C implementation of Dijkstra's algorithm.
Definition in file dijkstra.c.
Go to the source code of this file.
Functions | |
DIJKSTRA_Bool | dijkstraGraphIsValid (const DIJKSTRA_GRAPH *G) |
static DIJKSTRA_Bool | dijkstraHeapIsValid (const unsigned int *entry, const unsigned long long *value, const unsigned int *order, const unsigned int used, const unsigned int size) |
static void | dijkstraSiftDown (unsigned int *entry, const unsigned long long *value, unsigned int *order, unsigned int used, unsigned int current) |
static void | dijkstraSiftUp (unsigned int *entry, const unsigned long long *value, unsigned int *order, unsigned int current) |
unsigned int | dijkstra (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order) |
unsigned int | dijkstraPair (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order) |
unsigned int | dijkstraPairCutoff (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned long long cutoff, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order) |
unsigned int | dijkstraPairCutoffIgnore (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned int *ignore, unsigned long long cutoff, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order) |
DIJKSTRA_Bool dijkstraGraphIsValid | ( | const DIJKSTRA_GRAPH * | G | ) |
Check whether the data structures of the graph are valid.
G | directed graph to be checked |
Definition at line 32 of file dijkstra.c.
References DIJKSTRA_Graph::arcs, DIJKSTRA_UNUSED, DIJKSTRA_Graph::head, DIJKSTRA_Graph::maxweight, DIJKSTRA_Graph::minweight, DIJKSTRA_Graph::nodes, DIJKSTRA_Graph::outbeg, DIJKSTRA_Graph::outcnt, TRUE, and DIJKSTRA_Graph::weight.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), and separateGLS().
|
static |
Check whether heap is valid.
entry | entries of heap |
value | values in heap |
order | order of entries |
used | number of used entries |
size | size of entry array |
Definition at line 73 of file dijkstra.c.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), and dijkstraPairCutoffIgnore().
|
static |
Moves an entry down in the vector until the sorting is valid again.
entry | entries of heap |
value | values in heap |
order | order of entries |
used | number of used entries |
current | current entry to be sifted |
Definition at line 102 of file dijkstra.c.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), and dijkstraPairCutoffIgnore().
|
static |
Moves an entry up in the vector until the sorting is valid again.
entry | entries of heap |
value | values in heap |
order | order of entries |
current | current entry to be sifted |
Definition at line 147 of file dijkstra.c.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), and dijkstraPairCutoffIgnore().
unsigned int dijkstra | ( | const DIJKSTRA_GRAPH * | G, |
unsigned int | source, | ||
unsigned long long * | dist, | ||
unsigned int * | pred, | ||
unsigned int * | entry, | ||
unsigned int * | order | ||
) |
Dijkstra's algorithm for shortest paths from a single source using binary heaps
G | directed graph |
source | source node |
dist | node distances (allocated by user) |
pred | node predecessors in final shortest path tree (allocated by user) |
entry | temporary storage (for each node - must be allocated by user) |
order | temporary storage (for each node - must be allocated by user) |
Definition at line 180 of file dijkstra.c.
References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.
unsigned int dijkstraPair | ( | const DIJKSTRA_GRAPH * | G, |
unsigned int | source, | ||
unsigned int | target, | ||
unsigned long long * | dist, | ||
unsigned int * | pred, | ||
unsigned int * | entry, | ||
unsigned int * | order | ||
) |
Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps
G | directed graph |
source | source node |
target | target node |
dist | node distances (allocated by user) |
pred | node predecessors in final shortest path tree (allocated by user) |
entry | temporary storage (for each node - must be allocated by user) |
order | temporary storage (for each node - must be allocated by user) |
Definition at line 280 of file dijkstra.c.
References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.
unsigned int dijkstraPairCutoff | ( | const DIJKSTRA_GRAPH * | G, |
unsigned int | source, | ||
unsigned int | target, | ||
unsigned long long | cutoff, | ||
unsigned long long * | dist, | ||
unsigned int * | pred, | ||
unsigned int * | entry, | ||
unsigned int * | order | ||
) |
Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff
G | directed graph |
source | source node |
target | target node |
cutoff | if the distance of a node reached this value, we truncate the search |
dist | node distances (allocated by user) |
pred | node predecessors in final shortest path tree (allocated by user) |
entry | temporary storage (for each node - must be allocated by user) |
order | temporary storage (for each node - must be allocated by user) |
Definition at line 386 of file dijkstra.c.
References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.
Referenced by separateGLS().
unsigned int dijkstraPairCutoffIgnore | ( | const DIJKSTRA_GRAPH * | G, |
unsigned int | source, | ||
unsigned int | target, | ||
unsigned int * | ignore, | ||
unsigned long long | cutoff, | ||
unsigned long long * | dist, | ||
unsigned int * | pred, | ||
unsigned int * | entry, | ||
unsigned int * | order | ||
) |
Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff
G | directed graph |
source | source node |
target | target node |
ignore | marking nodes to be ignored (if value is nonzero) |
cutoff | if the distance of a node reached this value, we truncate the search |
dist | node distances (allocated by user) |
pred | node predecessors in final shortest path tree (allocated by user) |
entry | temporary storage (for each node - must be allocated by user) |
order | temporary storage (for each node - must be allocated by user) |
Definition at line 497 of file dijkstra.c.
References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.
Referenced by separateGLS().