equal
deleted
inserted
replaced
44 |
44 |
45 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
45 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
46 /// |
46 /// |
47 typedef LM LengthMap; |
47 typedef LM LengthMap; |
48 //The type of the length of the edges. |
48 //The type of the length of the edges. |
49 typedef typename LM::ValueType ValueType; |
49 typedef typename LM::Value Value; |
50 ///The heap type used by Dijkstra algorithm. |
50 ///The heap type used by Dijkstra algorithm. |
51 |
51 |
52 ///The heap type used by Dijkstra algorithm. |
52 ///The heap type used by Dijkstra algorithm. |
53 /// |
53 /// |
54 ///\sa BinHeap |
54 ///\sa BinHeap |
55 ///\sa Dijkstra |
55 ///\sa Dijkstra |
56 typedef BinHeap<typename Graph::Node, |
56 typedef BinHeap<typename Graph::Node, |
57 typename LM::ValueType, |
57 typename LM::Value, |
58 typename GR::template NodeMap<int>, |
58 typename GR::template NodeMap<int>, |
59 std::less<ValueType> > Heap; |
59 std::less<Value> > Heap; |
60 |
60 |
61 ///\brief The type of the map that stores the last |
61 ///\brief The type of the map that stores the last |
62 ///edges of the shortest paths. |
62 ///edges of the shortest paths. |
63 /// |
63 /// |
64 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
64 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
88 } |
88 } |
89 ///The type of the map that stores the dists of the nodes. |
89 ///The type of the map that stores the dists of the nodes. |
90 |
90 |
91 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
91 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
92 /// |
92 /// |
93 typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap; |
93 typedef typename Graph::template NodeMap<typename LM::Value> DistMap; |
94 ///Instantiates a DistMap. |
94 ///Instantiates a DistMap. |
95 |
95 |
96 ///\todo Please document... |
96 ///\todo Please document... |
97 /// |
97 /// |
98 static DistMap *createDistMap(const GR &G) |
98 static DistMap *createDistMap(const GR &G) |
107 ///The edge lengths are passed to the algorithm using a |
107 ///The edge lengths are passed to the algorithm using a |
108 ///\ref concept::ReadMap "ReadMap", |
108 ///\ref concept::ReadMap "ReadMap", |
109 ///so it is easy to change it to any kind of length. |
109 ///so it is easy to change it to any kind of length. |
110 /// |
110 /// |
111 ///The type of the length is determined by the |
111 ///The type of the length is determined by the |
112 ///\ref concept::ReadMap::ValueType "ValueType" of the length map. |
112 ///\ref concept::ReadMap::Value "Value" of the length map. |
113 /// |
113 /// |
114 ///It is also possible to change the underlying priority heap. |
114 ///It is also possible to change the underlying priority heap. |
115 /// |
115 /// |
116 ///\param GR The graph type the algorithm runs on. The default value is |
116 ///\param GR The graph type the algorithm runs on. The default value is |
117 ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it |
117 ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it |
156 typedef typename Graph::Edge Edge; |
156 typedef typename Graph::Edge Edge; |
157 ///\e |
157 ///\e |
158 typedef typename Graph::OutEdgeIt OutEdgeIt; |
158 typedef typename Graph::OutEdgeIt OutEdgeIt; |
159 |
159 |
160 ///The type of the length of the edges. |
160 ///The type of the length of the edges. |
161 typedef typename TR::LengthMap::ValueType ValueType; |
161 typedef typename TR::LengthMap::Value Value; |
162 ///The type of the map that stores the edge lengths. |
162 ///The type of the map that stores the edge lengths. |
163 typedef typename TR::LengthMap LengthMap; |
163 typedef typename TR::LengthMap LengthMap; |
164 ///\brief The type of the map that stores the last |
164 ///\brief The type of the map that stores the last |
165 ///edges of the shortest paths. |
165 ///edges of the shortest paths. |
166 typedef typename TR::PredMap PredMap; |
166 typedef typename TR::PredMap PredMap; |
385 heap.push(s,0); |
385 heap.push(s,0); |
386 |
386 |
387 while ( !heap.empty() ) { |
387 while ( !heap.empty() ) { |
388 |
388 |
389 Node v=heap.top(); |
389 Node v=heap.top(); |
390 ValueType oldvalue=heap[v]; |
390 Value oldvalue=heap[v]; |
391 heap.pop(); |
391 heap.pop(); |
392 distance->set(v, oldvalue); |
392 distance->set(v, oldvalue); |
393 |
393 |
394 |
394 |
395 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
395 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
418 |
418 |
419 ///Returns the distance of a node from the root. |
419 ///Returns the distance of a node from the root. |
420 ///\pre \ref run() must be called before using this function. |
420 ///\pre \ref run() must be called before using this function. |
421 ///\warning If node \c v in unreachable from the root the return value |
421 ///\warning If node \c v in unreachable from the root the return value |
422 ///of this funcion is undefined. |
422 ///of this funcion is undefined. |
423 ValueType dist(Node v) const { return (*distance)[v]; } |
423 Value dist(Node v) const { return (*distance)[v]; } |
424 |
424 |
425 ///Returns the 'previous edge' of the shortest path tree. |
425 ///Returns the 'previous edge' of the shortest path tree. |
426 |
426 |
427 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
427 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
428 ///i.e. it returns the last edge of a shortest path from the root to \c |
428 ///i.e. it returns the last edge of a shortest path from the root to \c |
495 typedef typename Graph::OutEdgeIt OutEdgeIt; |
495 typedef typename Graph::OutEdgeIt OutEdgeIt; |
496 |
496 |
497 ///The type of the map that stores the edge lengths. |
497 ///The type of the map that stores the edge lengths. |
498 typedef typename TR::LengthMap LengthMap; |
498 typedef typename TR::LengthMap LengthMap; |
499 ///The type of the length of the edges. |
499 ///The type of the length of the edges. |
500 typedef typename LengthMap::ValueType ValueType; |
500 typedef typename LengthMap::Value Value; |
501 ///\brief The type of the map that stores the last |
501 ///\brief The type of the map that stores the last |
502 ///edges of the shortest paths. |
502 ///edges of the shortest paths. |
503 typedef typename TR::PredMap PredMap; |
503 typedef typename TR::PredMap PredMap; |
504 ///\brief The type of the map that stores the last but one |
504 ///\brief The type of the map that stores the last but one |
505 ///nodes of the shortest paths. |
505 ///nodes of the shortest paths. |