abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
Shortest Path Algorithms

Algorithms for finding shortest paths. More...

Files

file  astar.h
file  bellman_ford.h
 Bellman-Ford algorithm.
file  bidir_dijkstra.h
file  dijkstra.h
file  suurballe.h

Classes

class  AStar< GR , LEN , HM , TR >
 A* algorithm for a shortest path between two nodes. More...
class  BellmanFord< GR , LEN , TR >
 BellmanFord algorithm class. More...
class  BidirDijkstra< GR , LEN , TR >
 Bidirectional Dijkstra algorithm for a shortest path between two nodes. 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...

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.

Detailed Description

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.

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 );
BellmanFordWizard< BellmanFordWizardBase< GR , LEN > > bellmanFord( const GR & digraph , const LEN & length )
Function type interface for the Bellman-Ford algorithm.
Definition bellman_ford.h:1145
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 );
DijkstraWizard< DijkstraWizardBase< GR , LEN > > dijkstra( const GR & digraph , const LEN & length )
Function-type interface for Dijkstra algorithm.
Definition dijkstra.h:1298
Warning
Don't forget to put the run() to the end of the parameter list.
See also
DijkstraWizard
Dijkstra