Shortest Path Algorithms

---

Detailed Description

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

• Dijkstra Dijkstra's algorithm for finding shortest paths from a source node when all arc lengths are non-negative.
• Suurballe A successive shortest path algorithm for finding arc-disjoint paths between two nodes having minimum total length.

Classes
class	Dijkstra< GR, LEN, TR >
	Dijkstra algorithm class. More...
class	Suurballe< GR, LEN >
	Algorithm for finding arc-disjoint paths between two nodes having minimum total length. More...
Files
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 >
DijkstraWizard < DijkstraWizardBase< GR, LEN > >	dijkstra (const GR &digraph, const LEN &length)
	Function-type interface for Dijkstra algorithm.

---

Function Documentation

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