dijkstra.c
Go to the documentation of this file.
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41 if ( G == NULL || G->outbeg == NULL || G->outcnt == NULL || G->weight == NULL || G->head == NULL )
386 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff */
391 unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
497 /** Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff */
503 unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
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)
Definition: dijkstra.c:281
static void dijkstraSiftUp(unsigned int *entry, const unsigned long long *value, unsigned int *order, unsigned int current)
Definition: dijkstra.c:148
Definitions for Disjkstra's shortest path algorithm.
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)
Definition: dijkstra.c:74
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)
Definition: dijkstra.c:387
DIJKSTRA_Bool dijkstraGraphIsValid(const DIJKSTRA_GRAPH *G)
Definition: dijkstra.c:33
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)
Definition: dijkstra.c:498
Definition: dijkstra.h:43
static void dijkstraSiftDown(unsigned int *entry, const unsigned long long *value, unsigned int *order, unsigned int used, unsigned int current)
Definition: dijkstra.c:103
unsigned int dijkstra(const DIJKSTRA_GRAPH *G, unsigned int source, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
Definition: dijkstra.c:181