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