equal
deleted
inserted
replaced
67 typename Heap> |
67 typename Heap> |
68 #else |
68 #else |
69 template <typename Graph, |
69 template <typename Graph, |
70 typename LengthMap=typename Graph::EdgeMap<int>, |
70 typename LengthMap=typename Graph::EdgeMap<int>, |
71 template <class,class,class> class Heap = BinHeap > |
71 template <class,class,class> class Heap = BinHeap > |
72 // typename Heap=BinHeap <typename Graph::Node, |
|
73 // typename LengthMap::ValueType, |
|
74 // typename Graph::NodeMap<int> > > |
|
75 #endif |
72 #endif |
76 class Dijkstra{ |
73 class Dijkstra{ |
77 public: |
74 public: |
78 typedef typename Graph::Node Node; |
75 typedef typename Graph::Node Node; |
79 typedef typename Graph::NodeIt NodeIt; |
76 typedef typename Graph::NodeIt NodeIt; |
87 |
84 |
88 private: |
85 private: |
89 const Graph& G; |
86 const Graph& G; |
90 const LengthMap& length; |
87 const LengthMap& length; |
91 PredMap predecessor; |
88 PredMap predecessor; |
92 //In place of reach: |
|
93 PredNodeMap pred_node; |
89 PredNodeMap pred_node; |
94 DistMap distance; |
90 DistMap distance; |
95 //I don't like this: |
|
96 // //FIXME: |
|
97 // typename Graph::NodeMap<bool> reach; |
|
98 // //typename Graph::NodeMap<int> reach; |
|
99 |
91 |
100 public : |
92 public : |
101 |
93 |
102 /* |
|
103 The distance of the nodes is 0. |
|
104 */ |
|
105 Dijkstra(Graph& _G, LengthMap& _length) : |
94 Dijkstra(Graph& _G, LengthMap& _length) : |
106 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
95 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
107 |
96 |
108 void run(Node s); |
97 void run(Node s); |
109 |
98 |
144 |
133 |
145 ///Returns a reference to the NodeMap of the last but one nodes of the |
134 ///Returns a reference to the NodeMap of the last but one nodes of the |
146 ///shortest paths. |
135 ///shortest paths. |
147 ///\pre \ref run() must be called before using this function. |
136 ///\pre \ref run() must be called before using this function. |
148 const PredNodeMap &predNodeMap() const { return pred_node;} |
137 const PredNodeMap &predNodeMap() const { return pred_node;} |
149 |
|
150 // bool reached(Node v) { return reach[v]; } |
|
151 |
138 |
152 ///Checks if a node is reachable from the source. |
139 ///Checks if a node is reachable from the source. |
153 |
140 |
154 ///Returns \c true if \c v is reachable from the source. |
141 ///Returns \c true if \c v is reachable from the source. |
155 ///\warning the source node is reported to be unreached! |
142 ///\warning the source node is reported to be unreached! |
184 // If a node is unreacheable, then why should be the dist=0? |
171 // If a node is unreacheable, then why should be the dist=0? |
185 // distance.set(u,0); |
172 // distance.set(u,0); |
186 // reach.set(u,false); |
173 // reach.set(u,false); |
187 } |
174 } |
188 |
175 |
189 //We don't need it at all. |
|
190 // //FIXME: |
|
191 // typename Graph::NodeMap<bool> scanned(G,false); |
|
192 // //typename Graph::NodeMap<int> scanned(G,false); |
|
193 typename Graph::NodeMap<int> heap_map(G,-1); |
176 typename Graph::NodeMap<int> heap_map(G,-1); |
194 |
177 |
195 //Heap heap(heap_map); |
|
196 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); |
178 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); |
197 |
179 |
198 heap.push(s,0); |
180 heap.push(s,0); |
199 // reach.set(s, true); |
|
200 |
181 |
201 while ( !heap.empty() ) { |
182 while ( !heap.empty() ) { |
202 |
183 |
203 Node v=heap.top(); |
184 Node v=heap.top(); |
204 ValueType oldvalue=heap[v]; |
185 ValueType oldvalue=heap[v]; |
209 G.valid(e); G.next(e)) { |
190 G.valid(e); G.next(e)) { |
210 Node w=G.head(e); |
191 Node w=G.head(e); |
211 |
192 |
212 switch(heap.state(w)) { |
193 switch(heap.state(w)) { |
213 case heap.PRE_HEAP: |
194 case heap.PRE_HEAP: |
214 // reach.set(w,true); |
|
215 heap.push(w,oldvalue+length[e]); |
195 heap.push(w,oldvalue+length[e]); |
216 predecessor.set(w,e); |
196 predecessor.set(w,e); |
217 pred_node.set(w,v); |
197 pred_node.set(w,v); |
218 break; |
198 break; |
219 case heap.IN_HEAP: |
199 case heap.IN_HEAP: |