Definitions for Disjkstra's shortest path algorithm.
Definition in file dijkstra.h.
Go to the source code of this file.
Data Structures | |
struct | DIJKSTRA_Graph |
Macros | |
#define | DIJKSTRA_Bool unsigned int |
#define | TRUE 1 |
#define | FALSE 0 |
#define | DIJKSTRA_FARAWAY 0xffffffffu |
#define | DIJKSTRA_UNUSED 0xffffffffu |
Functions | |
DIJKSTRA_Bool | dijkstraGraphIsValid (const DIJKSTRA_GRAPH *G) |
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) |
#define DIJKSTRA_Bool unsigned int |
type used for boolean values
Definition at line 40 of file dijkstra.h.
Referenced by dijkstraGraphIsValid(), and dijkstraHeapIsValid().
#define TRUE 1 |
boolean value TRUE
Definition at line 43 of file dijkstra.h.
#define FALSE 0 |
boolean value FALSE
Definition at line 44 of file dijkstra.h.
#define DIJKSTRA_FARAWAY 0xffffffffu |
node has distance 'infinity'
Definition at line 47 of file dijkstra.h.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), and separateGLS().
#define DIJKSTRA_UNUSED 0xffffffffu |
node is unused
Definition at line 48 of file dijkstra.h.
Referenced by checkArraySizesGLS(), dijkstra(), dijkstraGraphIsValid(), dijkstraPair(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), separateGLS(), and separateHeur().
typedef struct DIJKSTRA_Graph DIJKSTRA_GRAPH |
graph structure - use consecutive storage for arcs
Definition at line 65 of file dijkstra.h.
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 42 of file dijkstra.c.
References DIJKSTRA_Graph::arcs, DIJKSTRA_Bool, DIJKSTRA_UNUSED, DIJKSTRA_Graph::head, i, 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().
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 using binary heaps
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 190 of file dijkstra.c.
References assert(), DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, i, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, 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 290 of file dijkstra.c.
References assert(), DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, i, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, 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 396 of file dijkstra.c.
References assert(), cutoff, DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, i, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, 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 507 of file dijkstra.c.
References assert(), cutoff, DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, i, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, and DIJKSTRA_Graph::weight.
Referenced by separateGLS().