This class provides an efficient implementation of the Dijkstra algorithm.
The arc lengths are passed to the algorithm using a ReadMap, so it is easy to change it to any kind of length. The type of the length is determined by the Value of the length map. It is also possible to change the underlying priority heap.
There is also a functiontype interface for the Dijkstra algorithm, which is convenient in the simplier cases and it can be used easier.
GR  The type of the digraph the algorithm runs on. The default type is ListDigraph. 
LEN  A readable arc map that specifies the lengths of the arcs. It is read once for each arc, so the map may involve in relatively time consuming process to compute the arc lengths if it is necessary. The default map type is GR::ArcMap<int>. 
#include <lemon/dijkstra.h>
Classes  
struct  SetDistMap 
Named parameter for setting DistMap type. More...  
struct  SetHeap 
Named parameter for setting heap and cross reference types More...  
struct  SetOperationTraits 
Named parameter for setting OperationTraits type More...  
struct  SetPredMap 
Named parameter for setting PredMap type. More...  
struct  SetProcessedMap 
Named parameter for setting ProcessedMap type. More...  
struct  SetStandardHeap 
Named parameter for setting heap and cross reference types with automatic allocation More...  
struct  SetStandardProcessedMap 
Named parameter for setting ProcessedMap type to be Digraph::NodeMap<bool> . More...  
Public Types  
typedef TR::Digraph  Digraph 
The type of the digraph the algorithm runs on.  
typedef TR::LengthMap::Value  Value 
The type of the length of the arcs.  
typedef TR::LengthMap  LengthMap 
The type of the map that stores the arc lengths.  
typedef TR::PredMap  PredMap 
The type of the map that stores the predecessor arcs of the shortest paths.  
typedef TR::DistMap  DistMap 
The type of the map that stores the distances of the nodes.  
typedef TR::ProcessedMap  ProcessedMap 
The type of the map that indicates which nodes are processed.  
typedef PredMapPath< Digraph, PredMap >  Path 
The type of the paths.  
typedef TR::HeapCrossRef  HeapCrossRef 
The cross reference type used for the current heap.  
typedef TR::Heap  Heap 
The heap type used by the algorithm.  
typedef TR::OperationTraits  OperationTraits 
The operation traits class of the algorithm.  
typedef TR  Traits 
The traits class of the algorithm.  
Public Member Functions  
Dijkstra (const Digraph &g, const LengthMap &length)  
Constructor.  
~Dijkstra ()  
Destructor.  
Dijkstra &  lengthMap (const LengthMap &m) 
Sets the length map.  
Dijkstra &  predMap (PredMap &m) 
Sets the map that stores the predecessor arcs.  
Dijkstra &  processedMap (ProcessedMap &m) 
Sets the map that indicates which nodes are processed.  
Dijkstra &  distMap (DistMap &m) 
Sets the map that stores the distances of the nodes.  
Dijkstra &  heap (Heap &hp, HeapCrossRef &cr) 
Sets the heap and the cross reference used by algorithm.  
Execution Control  
The simplest way to execute the Dijkstra algorithm is to use one of the member functions called run().  
void  init () 
void  addSource (Node s, Value dst=OperationTraits::zero()) 
Adds a new source node.  
Node  processNextNode () 
Processes the next node in the priority heap.  
Node  nextNode () const 
The next node to be processed.  
bool  emptyQueue () const 
Returns false if there are nodes to be processed.  
int  queueSize () const 
Returns the number of the nodes to be processed.  
void  start () 
Executes the algorithm.  
void  start (Node t) 
Executes the algorithm until the given target node is processed.  
template<class NodeBoolMap >  
Node  start (const NodeBoolMap &nm) 
Executes the algorithm until a condition is met.  
void  run (Node s) 
Runs the algorithm from the given source node.  
bool  run (Node s, Node t) 
Finds the shortest path between s and t .  
Query Functions  
Path  path (Node t) const 
The shortest path to a node.  
Value  dist (Node v) const 
The distance of a node from the root(s).  
Arc  predArc (Node v) const 
Returns the 'previous arc' of the shortest path tree for a node.  
Node  predNode (Node v) const 
Returns the 'previous node' of the shortest path tree for a node.  
const DistMap &  distMap () const 
Returns a const reference to the node map that stores the distances of the nodes.  
const PredMap &  predMap () const 
Returns a const reference to the node map that stores the predecessor arcs.  
bool  reached (Node v) const 
Checks if a node is reached from the root(s).  
bool  processed (Node v) const 
Checks if a node is processed.  
Value  currentDist (Node v) const 
The current distance of a node from the root(s).  
Constructor.
g  The digraph the algorithm runs on. 
length  The length map used by the algorithm. 

inline 

inline 

inline 
Initializes the internal data structures.

inline 
Adds a new source node to the priority heap. The optional second parameter is the initial distance of the node.
The function checks if the node has already been added to the heap and it is pushed to the heap only if either it was not in the heap or the shortest path found till then is shorter than dst
.

inline 
Processes the next node in the priority heap.

inline 
Returns the next node to be processed or INVALID
if the priority heap is empty.

inline 
Returns false
if there are nodes to be processed in the priority heap.

inline 
Returns the number of the nodes to be processed in the priority heap.

inline 
Executes the algorithm.
This method runs the Dijkstra algorithm from the root node(s) in order to compute the shortest path to each node.
The algorithm computes
d.start()
is just a shortcut of the following code.

inline 
Executes the algorithm until the given target node is processed.
This method runs the Dijkstra algorithm from the root node(s) in order to compute the shortest path to t
.
The algorithm computes
t
,t
from the root(s).

inline 
Executes the algorithm until a condition is met.
This method runs the Dijkstra algorithm from the root node(s) in order to compute the shortest path to a node v
with nm[v]
true, if such a node can be found.
nm  A bool (or convertible) node map. The algorithm will stop when it reaches a node v with nm[v] true. 
v
with nm[v]
true or INVALID
if no such node was found.

inline 
This method runs the Dijkstra algorithm from node s
in order to compute the shortest path to each node.
The algorithm computes
d.run(s)
is just a shortcut of the following code.

inline 
This method runs the Dijkstra algorithm from node s
in order to compute the shortest path to node t
(it stops searching when t
is processed).
true
if t
is reachable form s
.d.run(s,t)
is just a shortcut of the following code.

inline 

inline 

inline 
This function returns the 'previous arc' of the shortest path tree for the node v
, i.e. it returns the last arc of a shortest path from a root to v
. It is INVALID
if v
is not reached from the root(s) or if v
is a root.
The shortest path tree used here is equal to the shortest path tree used in predNode().

inline 
This function returns the 'previous node' of the shortest path tree for the node v
, i.e. it returns the last but one node from a shortest path from a root to v
. It is INVALID
if v
is not reached from the root(s) or if v
is a root.
The shortest path tree used here is equal to the shortest path tree used in predArc().

inline 

inline 

inline 

inline 