Detailed Description
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 |
Typedefs | |
typedef struct DIJKSTRA_Graph | DIJKSTRA_GRAPH |
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) |
Macro Definition Documentation
◆ DIJKSTRA_Bool
#define DIJKSTRA_Bool unsigned int |
type used for boolean values
Definition at line 40 of file dijkstra.h.
◆ TRUE
#define TRUE 1 |
boolean value TRUE
Definition at line 43 of file dijkstra.h.
◆ FALSE
#define FALSE 0 |
boolean value FALSE
Definition at line 44 of file dijkstra.h.
◆ DIJKSTRA_FARAWAY
#define DIJKSTRA_FARAWAY 0xffffffffu |
node has distance 'infinity'
Definition at line 47 of file dijkstra.h.
Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), and separateGLS().
◆ DIJKSTRA_UNUSED
#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 Documentation
◆ DIJKSTRA_GRAPH
typedef struct DIJKSTRA_Graph DIJKSTRA_GRAPH |
graph structure - use consecutive storage for arcs
Definition at line 65 of file dijkstra.h.
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 42 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().
◆ 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 using binary heaps
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 190 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 290 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 396 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 507 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().