Shortest Path Algorithms

## Detailed Description

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

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

## 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. More...

template<typename GR , typename LEN >
DijkstraWizard
< DijkstraWizardBase< GR, LEN > >
dijkstra (const GR &digraph, const LEN &length)
Function-type interface for Dijkstra algorithm. More...

## Function Documentation

 BellmanFordWizard > 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.
BellmanFordWizard
BellmanFord
 DijkstraWizard > 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.