#include <lemon/dijkstra.h>
Inheritance diagram for Dijkstra:
The type of the length is determined by the Value of the length map.
It is also possible to change the underlying priority heap.
GR | The graph type the algorithm runs on. The default value is ListGraph. The value of GR is not used directly by Dijkstra, it is only passed to DijkstraDefaultTraits. | |
LM | This read-only EdgeMap determines the lengths of the edges. It is read once for each edge, so the map may involve in relatively time consuming process to compute the edge length if it is necessary. The default map type is Graph::EdgeMap<int>. The value of LM is not used directly by Dijkstra, it is only passed to DijkstraDefaultTraits. | |
TR | Traits class to set various data types used by the algorithm. The default traits class is DijkstraDefaultTraits<GR,LM>. See DijkstraDefaultTraits for the documentation of a Dijkstra traits class. |
Definition at line 173 of file dijkstra.h.
Public Types | |
typedef TR::Graph | Graph |
The type of the underlying graph. | |
typedef Graph::Node | Node |
| |
typedef Graph::NodeIt | NodeIt |
| |
typedef Graph::Edge | Edge |
| |
typedef Graph::OutEdgeIt | OutEdgeIt |
| |
typedef TR::LengthMap::Value | Value |
The type of the length of the edges. | |
typedef TR::LengthMap | LengthMap |
The type of the map that stores the edge lengths. | |
typedef TR::PredMap | PredMap |
The type of the map that stores the last edges of the shortest paths. | |
typedef TR::PredNodeMap | PredNodeMap |
The type of the map that stores the last but one nodes of the shortest paths. | |
typedef TR::ReachedMap | ReachedMap |
The type of the map indicating if a node is reached. | |
typedef TR::DistMap | DistMap |
The type of the map that stores the dists of the nodes. | |
typedef TR::Heap | Heap |
The heap type used by the dijkstra algorithm. | |
Public Member Functions | |
Dijkstra (const Graph &_G, const LengthMap &_length) | |
Constructor. | |
~Dijkstra () | |
Destructor. | |
Dijkstra & | lengthMap (const LengthMap &m) |
Sets the length map. | |
Dijkstra & | predMap (PredMap &m) |
Sets the map storing the predecessor edges. | |
Dijkstra & | predNodeMap (PredNodeMap &m) |
Sets the map storing the predecessor nodes. | |
Dijkstra & | distMap (DistMap &m) |
Sets the map storing the distances calculated by the algorithm. | |
Excetution control | |
The simplest way to execute the algorithm is to use one of the member functions called run (...). It you need more control on the execution, first you must call init(), then you can add several source nodes with addSource(). Finally start() will perform the actual path computation. | |
void | init () |
Initializes the internal data structures. | |
void | addSource (Node s, Value dst=0) |
Adds a new source node. | |
void | processNextNode () |
Processes the next node in the priority heap. | |
bool | emptyHeap () |
Returns false if there are nodes to be processed in the priority heap. | |
int | heapSize () |
Returns the number of the nodes to be processed in the priority heap. | |
void | start () |
Executes the algorithm. | |
void | start (Node dest) |
Executes the algorithm until dest is reached. | |
template<class NM> | |
void | start (const NM &nm) |
Executes the algorithm until a condition is met. | |
void | run (Node s) |
Runs Dijkstra algorithm from node s . | |
Value | run (Node s, Node t) |
Finds the shortest path between s and t . | |
Query Functions | |
The result of the Dijkstra algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called. | |
Value | dist (Node v) const |
The distance of a node from the root. | |
Edge | pred (Node v) const |
Returns the 'previous edge' of the shortest path tree. | |
Node | predNode (Node v) const |
Returns the 'previous node' of the shortest path tree. | |
const DistMap & | distMap () const |
Returns a reference to the NodeMap of distances. | |
const PredMap & | predMap () const |
Returns a reference to the shortest path tree map. | |
const PredNodeMap & | predNodeMap () const |
Returns a reference to the map of nodes of shortest paths. | |
bool | reached (Node v) |
Checks if a node is reachable from the root. | |
Classes | |
class | DefDistMap |
Named parameter for setting DistMap type More... | |
class | DefPredMap |
Named parameter for setting PredMap type More... | |
class | DefPredNodeMap |
Named parameter for setting PredNodeMap type More... | |
class | DefReachedMap |
Named parameter for setting ReachedMap type More... | |
class | DefReachedMapToBeDefaultMap |
Named parameter for setting the ReachedMap type to be Graph::NodeMap<bool>. More... | |
class | UninitializedParameter |
Exception for uninitialized parameters. More... |
|
Definition at line 370 of file dijkstra.h. |
|
Sets the length map.
Definition at line 392 of file dijkstra.h. |
|
Sets the map storing the predecessor edges. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
Definition at line 405 of file dijkstra.h. |
|
Sets the map storing the predecessor nodes. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
Definition at line 422 of file dijkstra.h. |
|
Sets the map storing the distances calculated by the algorithm. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
Definition at line 439 of file dijkstra.h. |
|
Initializes the internal data structures.
Definition at line 474 of file dijkstra.h. |
|
Adds a new source node to the priority heap. The optional second parameter is the initial distance of the node.
It 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 longer then Definition at line 495 of file dijkstra.h. |
|
Processes the next node in the priority heap.
Definition at line 510 of file dijkstra.h. |
|
Returns Definition at line 542 of file dijkstra.h. |
|
Returns the number of the nodes to be processed in the priority heap Definition at line 547 of file dijkstra.h. |
|
Executes the algorithm.
Definition at line 563 of file dijkstra.h. |
|
Executes the algorithm until
dest . The algorithm computes
Definition at line 582 of file dijkstra.h. |
|
Executes the algorithm until a condition is met.
Definition at line 598 of file dijkstra.h. |
|
This method runs the Dijkstra algorithm from a root node
Definition at line 619 of file dijkstra.h. |
|
Finds the shortest path between
Definition at line 638 of file dijkstra.h. |
|
Returns the distance of a node from the root.
Definition at line 661 of file dijkstra.h. |
|
For a node
Definition at line 673 of file dijkstra.h. |
|
For a node
Definition at line 683 of file dijkstra.h. |
|
Returns a reference to the NodeMap of distances.
Definition at line 690 of file dijkstra.h. |
|
Returns a reference to the NodeMap of the edges of the shortest path tree.
Definition at line 697 of file dijkstra.h. |
|
Returns a reference to the NodeMap of the last but one nodes of the shortest path tree.
Definition at line 704 of file dijkstra.h. |
|
Returns
Definition at line 713 of file dijkstra.h. |