Detailed Description
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) |
Function Documentation
◆ dijkstraGraphIsValid()
DIJKSTRA_Bool dijkstraGraphIsValid | ( | const DIJKSTRA_GRAPH * | G | ) |
Check whether the data structures of the graph are valid.
- Parameters
-
G directed graph to be checked
Definition at line 33 of file dijkstra.c.
References DIJKSTRA_Graph::arcs, DIJKSTRA_UNUSED, DIJKSTRA_Graph::head, DIJKSTRA_Graph::maxweight, DIJKSTRA_Graph::minweight, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, DIJKSTRA_Graph::outcnt, TRUE, and DIJKSTRA_Graph::weight.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), and separateGLS().
◆ dijkstraHeapIsValid()
|
static |
Check whether heap is valid.
- Note
- Sift up/down do not use order, only for the last the changed one is entered.
- Parameters
-
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 74 of file dijkstra.c.
References FALSE, NULL, and TRUE.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), and dijkstraPairCutoffIgnore().
◆ dijkstraSiftDown()
|
static |
Moves an entry down in the vector until the sorting is valid again.
- Parameters
-
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 103 of file dijkstra.c.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), and dijkstraPairCutoffIgnore().
◆ dijkstraSiftUp()
|
static |
Moves an entry up in the vector until the sorting is valid again.
- Parameters
-
entry entries of heap value values in heap order order of entries current current entry to be sifted
Definition at line 148 of file dijkstra.c.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), and dijkstraPairCutoffIgnore().
◆ dijkstra()
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
- Parameters
-
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 181 of file dijkstra.c.
References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.
◆ dijkstraPair()
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
- Parameters
-
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 281 of file dijkstra.c.
References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.
◆ dijkstraPairCutoff()
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
- Parameters
-
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 387 of file dijkstra.c.
References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.
Referenced by separateGLS().
◆ dijkstraPairCutoffIgnore()
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
- Parameters
-
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 498 of file dijkstra.c.
References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.
Referenced by separateGLS().