Shortest Path Algorithms

Detailed Description

This group contains the algorithms for finding shortest paths in digraphs [6].

• Dijkstra algorithm for finding shortest paths from a source node when all arc lengths are non-negative.
• Bellman-Ford algorithm for finding shortest paths from a source node when arc lenghts can be either positive or negative, but the digraph should not contain directed cycles with negative total length.
• Floyd-Warshall and Johnson algorithms for solving the all-pairs shortest paths problem when arc lenghts can be either positive or negative, but the digraph should not contain directed cycles with negative total length.
• Suurballe A successive shortest path algorithm for finding arc-disjoint paths between two nodes having minimum total length.

Classes
class	BellmanFord< GR, LEN, TR >
	BellmanFord algorithm class. More...
class	Dijkstra< GR, LEN, TR >
	Dijkstra algorithm class. More...
class	Suurballe< GR, LEN, TR >
	Algorithm for finding arc-disjoint paths between two nodes having minimum total length. More...
class	BellmanFord< GR, LEN, TR >::ActiveIt
	LEMON iterator for getting the active nodes. More...
struct	BellmanFord< GR, LEN, TR >::SetDistMap< T >
	Named parameter for setting DistMap type. More...
struct	BellmanFord< GR, LEN, TR >::SetOperationTraits< T >
	Named parameter for setting OperationTraits type. More...
struct	BellmanFord< GR, LEN, TR >::SetPredMap< T >
	Named parameter for setting PredMap type. More...
struct	Dijkstra< GR, LEN, TR >::SetDistMap< T >
	Named parameter for setting DistMap type. More...
struct	Dijkstra< GR, LEN, TR >::SetHeap< H, CR >
	Named parameter for setting heap and cross reference types More...
struct	Dijkstra< GR, LEN, TR >::SetOperationTraits< T >
	Named parameter for setting OperationTraits type More...
struct	Dijkstra< GR, LEN, TR >::SetPredMap< T >
	Named parameter for setting PredMap type. More...
struct	Dijkstra< GR, LEN, TR >::SetProcessedMap< T >
	Named parameter for setting ProcessedMap type. More...
struct	Dijkstra< GR, LEN, TR >::SetStandardHeap< H, CR >
	Named parameter for setting heap and cross reference types with automatic allocation More...
struct	Dijkstra< GR, LEN, TR >::SetStandardProcessedMap
	Named parameter for setting ProcessedMap type to be Digraph::NodeMap<bool>. More...
struct	Suurballe< GR, LEN, TR >::SetFlowMap< T >
struct	Suurballe< GR, LEN, TR >::SetHeap< H, CR >
	Named parameter for setting Heap and HeapCrossRef types. More...
struct	Suurballe< GR, LEN, TR >::SetPath< T >
	Named parameter for setting Path type. More...
struct	Suurballe< GR, LEN, TR >::SetPotentialMap< T >

Files
file	bellman_ford.h
	Bellman-Ford algorithm.
file	dijkstra.h
	Dijkstra algorithm.
file	suurballe.h
	An algorithm for finding arc-disjoint paths between two nodes having minimum total length.

Functions
template<typename GR , typename LEN >
BellmanFordWizard < BellmanFordWizardBase< GR, LEN > >	bellmanFord (const GR &digraph, const LEN &length)
	Function type interface for the Bellman-Ford algorithm.
template<typename GR , typename LEN >
DijkstraWizard < DijkstraWizardBase< GR, LEN > >	dijkstra (const GR &digraph, const LEN &length)
	Function-type interface for Dijkstra algorithm.

Function Documentation

BellmanFordWizard<BellmanFordWizardBase<GR,LEN> > lemon::bellmanFord	(	const GR &	digraph,
		const LEN &	length
	)

Function type interface for the Bellman-Ford algorithm.

This function also has several named parameters, they are declared as the members of class BellmanFordWizard. The following examples show how to use these parameters.

// Compute shortest path from node s to each node
bellmanFord(g,length).predMap(preds).distMap(dists).run(s);

// Compute shortest path from s to t
bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);

Warning

Don't forget to put the run() to the end of the parameter list.

See Also

BellmanFordWizard

BellmanFord

DijkstraWizard<DijkstraWizardBase<GR,LEN> > lemon::dijkstra	(	const GR &	digraph,
		const LEN &	length
	)

Function-type interface for Dijkstra algorithm.

This function also has several named parameters, they are declared as the members of class DijkstraWizard. The following examples show how to use these parameters.

// Compute shortest path from node s to each node
dijkstra(g,length).predMap(preds).distMap(dists).run(s);

// Compute shortest path from s to t
bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);

Warning

Don't forget to put the run() to the end of the parameter list.

See Also

DijkstraWizard

Dijkstra