All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Files | Functions
Shortest Path Algorithms
Algorithms

Detailed Description

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

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