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 |
|---|---|
A* algorithm for a shortest path between two nodes. |
|
BellmanFord algorithm class. |
|
Bidirectional Dijkstra algorithm for a shortest path between two nodes. |
|
Dijkstra algorithm class. |
|
Algorithm for finding arc-disjoint paths between two nodes having minimum total length. |
Other classes of its headers
Class |
Description |
|---|---|
The default traits class of AStar. |
|
Default OperationTraits for the BellmanFord algorithm class. |
|
Default traits class of BellmanFord class. |
|
Default traits class of bellmanFord() function. |
|
Default traits class used by BellmanFordWizard. |
|
Auxiliary class for the function-type interface of the Bellman-Ford algorithm. |
|
The default traits class of BidirDijkstra. |
|
Default operation traits for the Dijkstra algorithm class. |
|
Default traits class of Dijkstra class. |
|
Default traits class of dijkstra() function. |
|
Default traits class used by DijkstraWizard. |
|
Auxiliary class for the function-type interface of Dijkstra algorithm. |
|
Default traits class of Suurballe algorithm. |
Functions and other members
-
template< typename GR , typename LEN >
BellmanFordWizard< BellmanFordWizardBase< GR , LEN > > bellmanFord(
) 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
See also
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(
) 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
See also
Warning
Don’t forget to put the run() to the end of the parameter list.