Shortest Path Algorithms

The same group on the Doxygen site.

group Shortest Path Algorithms

Algorithms for finding shortest paths.

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

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

  • Bidirectional Dijkstra algorithm for finding a shortest path between two nodes when all arc lengths are non-negative, by a forward and a backward search that meet halfway.

  • A* algorithm for finding a shortest path between two nodes when all arc lengths are non-negative, by a search guided by an admissible estimate of the distance to the target.

  • Suurballe A successive shortest path algorithm for finding arc-disjoint paths between two nodes having minimum total length.

Classes

Class

Description

AStar

A* algorithm for a shortest path between two nodes.

BellmanFord

BellmanFord algorithm class.

BidirDijkstra

Bidirectional Dijkstra algorithm for a shortest path between two nodes.

Dijkstra

Dijkstra algorithm class.

Suurballe

Algorithm for finding arc-disjoint paths between two nodes having minimum total length.

Other classes of its headers

Class

Description

AStarDefaultTraits

The default traits class of AStar.

BellmanFordDefaultOperationTraits

Default OperationTraits for the BellmanFord algorithm class.

BellmanFordDefaultTraits

Default traits class of BellmanFord class.

BellmanFordWizardDefaultTraits

Default traits class of bellmanFord() function.

BellmanFordWizardBase

Default traits class used by BellmanFordWizard.

BellmanFordWizard

Auxiliary class for the function-type interface of the Bellman-Ford algorithm.

BidirDijkstraDefaultTraits

The default traits class of BidirDijkstra.

DijkstraDefaultOperationTraits

Default operation traits for the Dijkstra algorithm class.

DijkstraDefaultTraits

Default traits class of Dijkstra class.

DijkstraWizardDefaultTraits

Default traits class of dijkstra() function.

DijkstraWizardBase

Default traits class used by DijkstraWizard.

DijkstraWizard

Auxiliary class for the function-type interface of Dijkstra algorithm.

SuurballeDefaultTraits

Default traits class of Suurballe algorithm.

Functions and other members

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 );

See also

BellmanFord

Warning

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

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 );

See also

DijkstraWizard

See also

Dijkstra

Warning

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