35 ///The edge lengths are passed to the algorithm using a |
35 ///The edge lengths are passed to the algorithm using a |
36 ///\ref concept::ReadMap "ReadMap", |
36 ///\ref concept::ReadMap "ReadMap", |
37 ///so it is easy to change it to any kind of length. |
37 ///so it is easy to change it to any kind of length. |
38 /// |
38 /// |
39 ///The type of the length is determined by the |
39 ///The type of the length is determined by the |
40 ///\ref concept::ReadMap::ValueType "ValueType" of the length map. |
40 ///\ref concept::ReadMap::Value "Value" of the length map. |
41 /// |
41 /// |
42 ///It is also possible to change the underlying priority heap. |
42 ///It is also possible to change the underlying priority heap. |
43 /// |
43 /// |
44 ///\param GR The graph type the algorithm runs on. |
44 ///\param GR The graph type the algorithm runs on. |
45 ///\param LM This read-only |
45 ///\param LM This read-only |
79 typedef typename Graph::Edge Edge; |
79 typedef typename Graph::Edge Edge; |
80 ///\e |
80 ///\e |
81 typedef typename Graph::OutEdgeIt OutEdgeIt; |
81 typedef typename Graph::OutEdgeIt OutEdgeIt; |
82 |
82 |
83 ///The type of the length of the edges. |
83 ///The type of the length of the edges. |
84 typedef typename LM::ValueType ValueType; |
84 typedef typename LM::Value Value; |
85 ///The type of the map that stores the edge lengths. |
85 ///The type of the map that stores the edge lengths. |
86 typedef LM LengthMap; |
86 typedef LM LengthMap; |
87 ///\brief The type of the map that stores the last |
87 ///\brief The type of the map that stores the last |
88 ///edges of the shortest paths. |
88 ///edges of the shortest paths. |
89 typedef typename Graph::template NodeMap<Edge> PredMap; |
89 typedef typename Graph::template NodeMap<Edge> PredMap; |
90 ///\brief The type of the map that stores the last but one |
90 ///\brief The type of the map that stores the last but one |
91 ///nodes of the shortest paths. |
91 ///nodes of the shortest paths. |
92 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
92 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
93 ///The type of the map that stores the dists of the nodes. |
93 ///The type of the map that stores the dists of the nodes. |
94 typedef typename Graph::template NodeMap<ValueType> DistMap; |
94 typedef typename Graph::template NodeMap<Value> DistMap; |
95 |
95 |
96 private: |
96 private: |
97 /// Pointer to the underlying graph. |
97 /// Pointer to the underlying graph. |
98 const Graph *G; |
98 const Graph *G; |
99 /// Pointer to the length map |
99 /// Pointer to the length map |
235 pred_node->set(u,INVALID); |
235 pred_node->set(u,INVALID); |
236 } |
236 } |
237 |
237 |
238 typename GR::template NodeMap<int> heap_map(*G,-1); |
238 typename GR::template NodeMap<int> heap_map(*G,-1); |
239 |
239 |
240 typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, |
240 typedef Heap<Node, Value, typename GR::template NodeMap<int>, |
241 std::less<ValueType> > |
241 std::less<Value> > |
242 HeapType; |
242 HeapType; |
243 |
243 |
244 HeapType heap(heap_map); |
244 HeapType heap(heap_map); |
245 |
245 |
246 heap.push(s,0); |
246 heap.push(s,0); |
247 |
247 |
248 while ( !heap.empty() ) { |
248 while ( !heap.empty() ) { |
249 |
249 |
250 Node v=heap.top(); |
250 Node v=heap.top(); |
251 ValueType oldvalue=heap[v]; |
251 Value oldvalue=heap[v]; |
252 heap.pop(); |
252 heap.pop(); |
253 distance->set(v, oldvalue); |
253 distance->set(v, oldvalue); |
254 |
254 |
255 |
255 |
256 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
256 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
279 |
279 |
280 ///Returns the distance of a node from the root. |
280 ///Returns the distance of a node from the root. |
281 ///\pre \ref run() must be called before using this function. |
281 ///\pre \ref run() must be called before using this function. |
282 ///\warning If node \c v in unreachable from the root the return value |
282 ///\warning If node \c v in unreachable from the root the return value |
283 ///of this funcion is undefined. |
283 ///of this funcion is undefined. |
284 ValueType dist(Node v) const { return (*distance)[v]; } |
284 Value dist(Node v) const { return (*distance)[v]; } |
285 |
285 |
286 ///Returns the 'previous edge' of the shortest path tree. |
286 ///Returns the 'previous edge' of the shortest path tree. |
287 |
287 |
288 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
288 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
289 ///i.e. it returns the last edge of a shortest path from the root to \c |
289 ///i.e. it returns the last edge of a shortest path from the root to \c |