19 ///This class provides an efficient implementation of %Dijkstra algorithm. |
19 ///This class provides an efficient implementation of %Dijkstra algorithm. |
20 ///The edge lengths are passed to the algorithm using a |
20 ///The edge lengths are passed to the algorithm using a |
21 ///\ref ReadMap "readable map", |
21 ///\ref ReadMap "readable map", |
22 ///so it is easy to change it to any kind of length. |
22 ///so it is easy to change it to any kind of length. |
23 /// |
23 /// |
24 ///The type of the length is determined by the \c ValueType of the length map. |
24 ///The type of the length is determined by the \c Value of the length map. |
25 /// |
25 /// |
26 ///It is also possible to change the underlying priority heap. |
26 ///It is also possible to change the underlying priority heap. |
27 /// |
27 /// |
28 ///\param GR The graph type the algorithm runs on. |
28 ///\param GR The graph type the algorithm runs on. |
29 ///\param LM This read-only |
29 ///\param LM This read-only |
57 typedef typename Graph::NodeIt NodeIt; |
57 typedef typename Graph::NodeIt NodeIt; |
58 typedef typename Graph::Edge Edge; |
58 typedef typename Graph::Edge Edge; |
59 typedef typename Graph::OutEdgeIt OutEdgeIt; |
59 typedef typename Graph::OutEdgeIt OutEdgeIt; |
60 |
60 |
61 ///The type of the length of the edges. |
61 ///The type of the length of the edges. |
62 typedef typename LM::ValueType ValueType; |
62 typedef typename LM::Value Value; |
63 ///The type of the map that stores the edge lengths. |
63 ///The type of the map that stores the edge lengths. |
64 typedef LM LengthMap; |
64 typedef LM LengthMap; |
65 ///\brief The type of the map that stores the last |
65 ///\brief The type of the map that stores the last |
66 ///edges of the shortest paths. |
66 ///edges of the shortest paths. |
67 typedef typename Graph::template NodeMap<Edge> PredMap; |
67 typedef typename Graph::template NodeMap<Edge> PredMap; |
68 ///\brief The type of the map that stores the last but one |
68 ///\brief The type of the map that stores the last but one |
69 ///nodes of the shortest paths. |
69 ///nodes of the shortest paths. |
70 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
70 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
71 ///The type of the map that stores the dists of the nodes. |
71 ///The type of the map that stores the dists of the nodes. |
72 typedef typename Graph::template NodeMap<ValueType> DistMap; |
72 typedef typename Graph::template NodeMap<Value> DistMap; |
73 |
73 |
74 private: |
74 private: |
75 const Graph *G; |
75 const Graph *G; |
76 const LM *length; |
76 const LM *length; |
77 // bool local_length; |
77 // bool local_length; |
214 pred_node->set(u,INVALID); |
214 pred_node->set(u,INVALID); |
215 } |
215 } |
216 |
216 |
217 typename GR::template NodeMap<int> heap_map(*G,-1); |
217 typename GR::template NodeMap<int> heap_map(*G,-1); |
218 |
218 |
219 typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, |
219 typedef Heap<Node, Value, typename GR::template NodeMap<int>, |
220 std::less<ValueType> > |
220 std::less<Value> > |
221 HeapType; |
221 HeapType; |
222 |
222 |
223 HeapType heap(heap_map); |
223 HeapType heap(heap_map); |
224 |
224 |
225 heap.push(s,0); |
225 heap.push(s,0); |
226 |
226 |
227 while ( !heap.empty() ) { |
227 while ( !heap.empty() ) { |
228 |
228 |
229 Node v=heap.top(); |
229 Node v=heap.top(); |
230 ValueType oldvalue=heap[v]; |
230 Value oldvalue=heap[v]; |
231 heap.pop(); |
231 heap.pop(); |
232 distance->set(v, oldvalue); |
232 distance->set(v, oldvalue); |
233 |
233 |
234 |
234 |
235 for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) { |
235 for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) { |
259 |
259 |
260 ///Returns the distance of a node from the root. |
260 ///Returns the distance of a node from the root. |
261 ///\pre \ref run() must be called before using this function. |
261 ///\pre \ref run() must be called before using this function. |
262 ///\warning If node \c v in unreachable from the root the return value |
262 ///\warning If node \c v in unreachable from the root the return value |
263 ///of this funcion is undefined. |
263 ///of this funcion is undefined. |
264 ValueType dist(Node v) const { return (*distance)[v]; } |
264 Value dist(Node v) const { return (*distance)[v]; } |
265 |
265 |
266 ///Returns the 'previous edge' of the shortest path tree. |
266 ///Returns the 'previous edge' of the shortest path tree. |
267 |
267 |
268 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
268 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
269 ///i.e. it returns the last edge from a shortest path from the root to \c |
269 ///i.e. it returns the last edge from a shortest path from the root to \c |