abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
BidirDijkstra< GR , LEN , TR > Class Template Reference

Bidirectional Dijkstra algorithm for a shortest path between two nodes. More...

#include <lemon/bidir_dijkstra.h>

Classes

struct  SetHeap
 Named parameter for setting the type of the heaps. More...

Public Types

typedef GR Digraph
 The digraph type of the algorithm.
typedef LEN LengthMap
 The type of the map of the arc lengths.
typedef LengthMap::Value Value
 The type of the lengths.
typedef lemon::Path< Digraph > Path
 The type of the shortest path.
typedef TR::HeapCrossRef HeapCrossRef
 The type of the cross reference maps of the heaps.
typedef TR::Heap Heap
 The type of the heaps of the two searches.

Public Member Functions

 BidirDijkstra (const Digraph &graph, const LengthMap &length)
 Constructor.
bool run (const Node &s, const Node &t)
 Find a shortest path from s to t.
Query Functions

The results of the last run() that returned true.

Value dist () const
 Return the length of a shortest path.
const Path & path () const
 Return a shortest path, empty if the source is the target.

Detailed Description

template< typename GR , typename LEN = typename GR::template ArcMap< int > , typename TR = BidirDijkstraDefaultTraits< GR , LEN > >
class lemon::BidirDijkstra< GR , LEN , TR >

This class finds a shortest path from a source to a target node of a digraph with nonnegative arc lengths, by two searches of Dijkstra's algorithm, a forward one from the source along the arcs and a backward one from the target against them, which grow alternately, the one whose smallest tentative distance is smaller. Each arc that joins the two searches gives a path, and the shortest one found is optimal as soon as the smallest tentative distances of the two searches sum to at least its length; the searches then stop, usually having scanned far fewer nodes than a search from the source alone.

One object answers any number of queries, each with run(), in time proportional to the part of the digraph that it scans.

Template Parameters
GRThe digraph type the algorithm runs on.
LENThe type of the map of the arc lengths, whose values must be nonnegative.
TRThe traits class, which gives the type of the heaps of the two searches [see BidirDijkstraDefaultTraits and SetHeap].

Constructor & Destructor Documentation

◆ BidirDijkstra()

template< typename GR , typename LEN = typename GR::template ArcMap< int > , typename TR = BidirDijkstraDefaultTraits< GR , LEN > >
BidirDijkstra ( const Digraph & graph,
const LengthMap & length )
inline

Constructor.

Parameters
graphThe digraph the algorithm runs on.
lengthThe lengths of the arcs, which must be nonnegative.

Member Function Documentation

◆ run()

template< typename GR , typename LEN = typename GR::template ArcMap< int > , typename TR = BidirDijkstraDefaultTraits< GR , LEN > >
bool run ( const Node & s,
const Node & t )
inline
Returns
true if t is reachable from s; its distance and a shortest path are then given by dist() and path().