![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
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 | |
| 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. | |
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.
| 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]. |
|
inline |
Constructor.
| graph | The digraph the algorithm runs on. |
| length | The lengths of the arcs, which must be nonnegative. |