1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file dijkstra.h 26 * @brief Definitions for Disjkstra's shortest path algorithm 27 * @author Thorsten Koch 28 * @author Marc Pfetsch 29 */ 30 31 #ifndef DIJSKSTRA_H 32 #define DIJSKSTRA_H 33 34 #ifdef __cplusplus 35 extern "C" { 36 #endif 37 38 /* declare own bools, if necessary */ 39 #ifndef DIJKSTRA_Bool 40 #define DIJKSTRA_Bool unsigned int /**< type used for boolean values */ 41 #endif 42 #ifndef TRUE 43 #define TRUE 1 /**< boolean value TRUE */ 44 #define FALSE 0 /**< boolean value FALSE */ 45 #endif 46 47 #define DIJKSTRA_FARAWAY 0xffffffffu /**< node has distance 'infinity' */ 48 #define DIJKSTRA_UNUSED 0xffffffffu /**< node is unused */ 49 50 51 /** graph structure - use consecutive storage for arcs */ 52 struct DIJKSTRA_Graph 53 { 54 unsigned int nodes; /**< number of nodes */ 55 unsigned int* outbeg; /**< indices of out-arcs for each node in arcs array */ 56 unsigned int* outcnt; /**< number of out-arcs for each node */ 57 unsigned int arcs; /**< consecutive storage for all arcs */ 58 unsigned int* weight; /**< corresponding weights for all arcs */ 59 unsigned int* head; /**< target nodes for all arcs */ 60 unsigned int minweight; /**< total minimal weight */ 61 unsigned int maxweight; /**< total maximal weight */ 62 }; 63 64 /** graph structure - use consecutive storage for arcs */ 65 typedef struct DIJKSTRA_Graph DIJKSTRA_GRAPH; 66 67 68 69 /** Check whether the data structures of the graph are valid. */ 70 DIJKSTRA_Bool dijkstraGraphIsValid( 71 const DIJKSTRA_GRAPH* G /**< directed graph to be checked */ 72 ); 73 74 /** Dijkstra's algorithm using binary heaps */ 75 unsigned int dijkstra( 76 const DIJKSTRA_GRAPH* G, /**< directed graph */ 77 unsigned int source, /**< source node */ 78 unsigned long long* dist, /**< node distances (allocated by user) */ 79 unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */ 80 unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */ 81 unsigned int* order /**< temporary storage (for each node - must be allocated by user) */ 82 ); 83 84 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps */ 85 unsigned int dijkstraPair( 86 const DIJKSTRA_GRAPH* G, /**< directed graph */ 87 unsigned int source, /**< source node */ 88 unsigned int target, /**< target node */ 89 unsigned long long* dist, /**< node distances (allocated by user) */ 90 unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */ 91 unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */ 92 unsigned int* order /**< temporary storage (for each node - must be allocated by user) */ 93 ); 94 95 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff */ 96 unsigned int dijkstraPairCutoff( 97 const DIJKSTRA_GRAPH* G, /**< directed graph */ 98 unsigned int source, /**< source node */ 99 unsigned int target, /**< target node */ 100 unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */ 101 unsigned long long* dist, /**< node distances (allocated by user) */ 102 unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */ 103 unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */ 104 unsigned int* order /**< temporary storage (for each node - must be allocated by user) */ 105 ); 106 107 /** Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff */ 108 unsigned int dijkstraPairCutoffIgnore( 109 const DIJKSTRA_GRAPH* G, /**< directed graph */ 110 unsigned int source, /**< source node */ 111 unsigned int target, /**< target node */ 112 unsigned int* ignore, /**< marking nodes to be ignored (if value is nonzero) */ 113 unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */ 114 unsigned long long* dist, /**< node distances (allocated by user) */ 115 unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */ 116 unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */ 117 unsigned int* order /**< temporary storage (for each node - must be allocated by user) */ 118 ); 119 120 #ifdef __cplusplus 121 } 122 #endif 123 124 #endif 125