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 ValueType 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 Graph The graph type the algorithm runs on. |
28 ///\param GR The graph type the algorithm runs on. |
29 ///\param LengthMap This read-only |
29 ///\param LM This read-only |
30 ///EdgeMap |
30 ///EdgeMap |
31 ///determines the |
31 ///determines the |
32 ///lengths of the edges. It is read once for each edge, so the map |
32 ///lengths of the edges. It is read once for each edge, so the map |
33 ///may involve in relatively time consuming process to compute the edge |
33 ///may involve in relatively time consuming process to compute the edge |
34 ///length if it is necessary. The default map type is |
34 ///length if it is necessary. The default map type is |
36 ///\param Heap The heap type used by the %Dijkstra |
36 ///\param Heap The heap type used by the %Dijkstra |
37 ///algorithm. The default |
37 ///algorithm. The default |
38 ///is using \ref BinHeap "binary heap". |
38 ///is using \ref BinHeap "binary heap". |
39 /// |
39 /// |
40 ///\author Jacint Szabo |
40 ///\author Jacint Szabo |
41 ///\todo We need a LengthMap typedef |
41 ///\todo We need a typedef-names should be standardized. |
|
42 |
42 #ifdef DOXYGEN |
43 #ifdef DOXYGEN |
43 template <typename Graph, |
44 template <typename GR, |
44 typename LengthMap, |
45 typename LM, |
45 typename Heap> |
46 typename Heap> |
46 #else |
47 #else |
47 template <typename Graph, |
48 template <typename GR, |
48 typename LengthMap=typename Graph::template EdgeMap<int>, |
49 typename LM=typename GR::template EdgeMap<int>, |
49 template <class,class,class,class> class Heap = BinHeap > |
50 template <class,class,class,class> class Heap = BinHeap > |
50 #endif |
51 #endif |
51 class Dijkstra{ |
52 class Dijkstra{ |
52 public: |
53 public: |
|
54 ///The type of the underlying graph. |
|
55 typedef GR Graph; |
53 typedef typename Graph::Node Node; |
56 typedef typename Graph::Node Node; |
54 typedef typename Graph::NodeIt NodeIt; |
57 typedef typename Graph::NodeIt NodeIt; |
55 typedef typename Graph::Edge Edge; |
58 typedef typename Graph::Edge Edge; |
56 typedef typename Graph::OutEdgeIt OutEdgeIt; |
59 typedef typename Graph::OutEdgeIt OutEdgeIt; |
57 |
60 |
58 typedef typename LengthMap::ValueType ValueType; |
61 ///The type of the length of the edges. |
|
62 typedef typename LM::ValueType ValueType; |
|
63 ///The the type of the map that stores the edge lengths. |
|
64 typedef LM LengthMap; |
|
65 ///\brief The the type of the map that stores the last |
|
66 ///edges of the shortest paths. |
59 typedef typename Graph::template NodeMap<Edge> PredMap; |
67 typedef typename Graph::template NodeMap<Edge> PredMap; |
|
68 ///\brief The the type of the map that stores the last but one |
|
69 ///nodes of the shortest paths. |
60 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
70 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
|
71 ///The the type of the map that stores the dists of the nodes. |
61 typedef typename Graph::template NodeMap<ValueType> DistMap; |
72 typedef typename Graph::template NodeMap<ValueType> DistMap; |
62 |
73 |
63 private: |
74 private: |
64 const Graph& G; |
75 const Graph& G; |
65 const LengthMap& length; |
76 const LM& length; |
66 PredMap predecessor; |
77 PredMap predecessor; |
67 PredNodeMap pred_node; |
78 PredNodeMap pred_node; |
68 DistMap distance; |
79 DistMap distance; |
69 |
80 |
70 public : |
81 public : |
71 |
82 |
72 Dijkstra(const Graph& _G, const LengthMap& _length) : |
83 Dijkstra(const Graph& _G, const LM& _length) : |
73 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
84 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
74 |
85 |
75 void run(Node s); |
86 void run(Node s); |
76 |
87 |
77 ///The distance of a node from the root. |
88 ///The distance of a node from the root. |
80 ///\pre \ref run() must be called before using this function. |
91 ///\pre \ref run() must be called before using this function. |
81 ///\warning If node \c v in unreachable from the root the return value |
92 ///\warning If node \c v in unreachable from the root the return value |
82 ///of this funcion is undefined. |
93 ///of this funcion is undefined. |
83 ValueType dist(Node v) const { return distance[v]; } |
94 ValueType dist(Node v) const { return distance[v]; } |
84 |
95 |
85 ///Returns the previous edge of the shortest path tree. |
96 ///Returns the 'previous edge' of the shortest path tree. |
86 |
97 |
87 ///For a node \c v it returns the previous edge of the shortest path tree, |
98 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
88 ///i.e. it returns the last edge from a shortest path from the root to \c |
99 ///i.e. it returns the last edge from a shortest path from the root to \c |
89 ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The |
100 ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The |
90 ///shortest path tree used here is equal to the shortest path tree used in |
101 ///shortest path tree used here is equal to the shortest path tree used in |
91 ///\ref predNode(Node v). \pre \ref run() must be called before using |
102 ///\ref predNode(Node v). \pre \ref run() must be called before using |
92 ///this function. |
103 ///this function. |
93 Edge pred(Node v) const { return predecessor[v]; } |
104 Edge pred(Node v) const { return predecessor[v]; } |
94 |
105 |
95 ///Returns the previous node of the shortest path tree. |
106 ///Returns the 'previous node' of the shortest path tree. |
96 |
107 |
97 ///For a node \c v it returns the previous node of the shortest path tree, |
108 ///For a node \c v it returns the 'previous node' of the shortest path tree, |
98 ///i.e. it returns the last but one node from a shortest path from the |
109 ///i.e. it returns the last but one node from a shortest path from the |
99 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if |
110 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if |
100 ///\c v=s. The shortest path tree used here is equal to the shortest path |
111 ///\c v=s. The shortest path tree used here is equal to the shortest path |
101 ///tree used in \ref pred(Node v). \pre \ref run() must be called before |
112 ///tree used in \ref pred(Node v). \pre \ref run() must be called before |
102 ///using this function. |
113 ///using this function. |
144 ///in order to |
155 ///in order to |
145 ///compute the |
156 ///compute the |
146 ///shortest path to each node. The algorithm computes |
157 ///shortest path to each node. The algorithm computes |
147 ///- The shortest path tree. |
158 ///- The shortest path tree. |
148 ///- The distance of each node from the root. |
159 ///- The distance of each node from the root. |
149 template <typename Graph, typename LengthMap, |
160 template <typename GR, typename LM, |
150 template<class,class,class,class> class Heap > |
161 template<class,class,class,class> class Heap > |
151 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
162 void Dijkstra<GR,LM,Heap>::run(Node s) { |
152 |
163 |
153 NodeIt u; |
164 NodeIt u; |
154 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
165 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
155 predecessor.set(u,INVALID); |
166 predecessor.set(u,INVALID); |
156 pred_node.set(u,INVALID); |
167 pred_node.set(u,INVALID); |
157 } |
168 } |
158 |
169 |
159 typename Graph::template NodeMap<int> heap_map(G,-1); |
170 typename GR::template NodeMap<int> heap_map(G,-1); |
160 |
171 |
161 typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>, |
172 typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, |
162 std::less<ValueType> > |
173 std::less<ValueType> > |
163 HeapType; |
174 HeapType; |
164 |
175 |
165 HeapType heap(heap_map); |
176 HeapType heap(heap_map); |
166 |
177 |