BidirDijkstra
Declared in lemon/bidir_dijkstra.h, in the group Shortest Path Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename LEN = typename GR::template ArcMap< int > , typename TR = BidirDijkstraDefaultTraits< GR , LEN > >
class BidirDijkstra Bidirectional Dijkstra algorithm for a shortest path between two nodes.
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:
GR – The digraph type the algorithm runs on.
LEN – The type of the map of the arc lengths, whose values must be nonnegative.
TR – The traits class, which gives the type of the heaps of the two searches [see BidirDijkstraDefaultTraits and SetHeap].
Query Functions
The results of the last run() that returned
true.Public Types
Public Functions
-
template< typename H , typename CR = typename Digraph::template NodeMap< int > >
struct SetHeap Named parameter for setting the type of the heaps.
The heaps of the two searches are of type
H, with cross reference maps of typeCR, e.g., a FibHeap or a RadixHeap in place of the BinHeap of the default.Public Types
-
typedef BidirDijkstra< GR , LEN , Traits > Create
-
typedef BidirDijkstra< GR , LEN , Traits > Create