Loading...
Searching...
No Matches
Shortest Path Algorithms
Algorithms

## Detailed Description

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

- 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
file | suurballe.h

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

## bellmanFord()

template<typename GR, typename LEN>

BellmanFordWizard< BellmanFordWizardBase< GR, LEN > > 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);
lemon::bellmanFord
BellmanFordWizard< BellmanFordWizardBase< GR, LEN > > bellmanFord(const GR &digraph, const LEN &length)
Function type interface for the Bellman-Ford algorithm.
Definition bellman_ford.h:1107

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

See also
  BellmanFordWizard
  BellmanFord

## dijkstra()

template<typename GR, typename LEN>

DijkstraWizard< DijkstraWizardBase< GR, LEN > > 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);
lemon::dijkstra
DijkstraWizard< DijkstraWizardBase< GR, LEN > > dijkstra(const GR &digraph, const LEN &length)
Function-type interface for Dijkstra algorithm.
Definition dijkstra.h:1296

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

See also
  DijkstraWizard
  Dijkstra