dijkstra.c File Reference

Detailed Description

C implementation of Dijkstra's algorithm.

Author

Thorsten Koch

Marc Pfetsch

Definition in file dijkstra.c.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "dijkstra.h"

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

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 32 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().

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

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 73 of file dijkstra.c.

References FALSE, NULL, and TRUE.

Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), and dijkstraPairCutoffIgnore().

static void dijkstraSiftDown ( unsigned int *  entry, const unsigned long long *  value, unsigned int *  order, unsigned int  used, unsigned int  current  )

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 102 of file dijkstra.c.

Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), and dijkstraPairCutoffIgnore().

static void dijkstraSiftUp ( unsigned int *  entry, const unsigned long long *  value, unsigned int *  order, unsigned int  current  )

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 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

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 180 of file dijkstra.c.

References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, 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

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 280 of file dijkstra.c.

References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, 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

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 386 of file dijkstra.c.

References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, 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

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 497 of file dijkstra.c.

References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, and DIJKSTRA_Graph::weight.

Referenced by separateGLS().