equal
deleted
inserted
replaced
66 typename LengthMap, |
66 typename LengthMap, |
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 typename Heap=BinHeap <typename Graph::Node, |
71 template <class,class,class> class Heap = BinHeap > |
72 typename LengthMap::ValueType, |
72 // typename Heap=BinHeap <typename Graph::Node, |
73 typename Graph::NodeMap<int> > > |
73 // typename LengthMap::ValueType, |
|
74 // typename Graph::NodeMap<int> > > |
74 #endif |
75 #endif |
75 class Dijkstra{ |
76 class Dijkstra{ |
76 public: |
77 public: |
77 typedef typename Graph::Node Node; |
78 typedef typename Graph::Node Node; |
78 typedef typename Graph::NodeIt NodeIt; |
79 typedef typename Graph::NodeIt NodeIt; |
102 The distance of the nodes is 0. |
103 The distance of the nodes is 0. |
103 */ |
104 */ |
104 Dijkstra(Graph& _G, LengthMap& _length) : |
105 Dijkstra(Graph& _G, LengthMap& _length) : |
105 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
106 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
106 |
107 |
107 |
|
108 void run(Node s); |
108 void run(Node s); |
109 |
109 |
110 ///The distance of a node from the source. |
110 ///The distance of a node from the source. |
111 |
111 |
112 ///Returns the distance of a node from the source. |
112 ///Returns the distance of a node from the source. |
171 ///in order to |
171 ///in order to |
172 ///compute the |
172 ///compute the |
173 ///shortest path to each node. The algorithm computes |
173 ///shortest path to each node. The algorithm computes |
174 ///- The shortest path tree. |
174 ///- The shortest path tree. |
175 ///- The distance of each node from the source. |
175 ///- The distance of each node from the source. |
176 template <typename Graph, typename LengthMap, typename Heap > |
176 template <typename Graph, typename LengthMap, |
|
177 template<class,class,class> class Heap > |
177 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
178 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
178 |
179 |
179 NodeIt u; |
180 NodeIt u; |
180 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
181 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
181 predecessor.set(u,INVALID); |
182 predecessor.set(u,INVALID); |
189 // //FIXME: |
190 // //FIXME: |
190 // typename Graph::NodeMap<bool> scanned(G,false); |
191 // typename Graph::NodeMap<bool> scanned(G,false); |
191 // //typename Graph::NodeMap<int> scanned(G,false); |
192 // //typename Graph::NodeMap<int> scanned(G,false); |
192 typename Graph::NodeMap<int> heap_map(G,-1); |
193 typename Graph::NodeMap<int> heap_map(G,-1); |
193 |
194 |
194 Heap heap(heap_map); |
195 //Heap heap(heap_map); |
|
196 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); |
195 |
197 |
196 heap.push(s,0); |
198 heap.push(s,0); |
197 // reach.set(s, true); |
199 // reach.set(s, true); |
198 |
200 |
199 while ( !heap.empty() ) { |
201 while ( !heap.empty() ) { |
205 |
207 |
206 for(OutEdgeIt e(G,v); G.valid(e); G.next(e)) { |
208 for(OutEdgeIt e(G,v); G.valid(e); G.next(e)) { |
207 Node w=G.head(e); |
209 Node w=G.head(e); |
208 |
210 |
209 switch(heap.state(w)) { |
211 switch(heap.state(w)) { |
210 case Heap::PRE_HEAP: |
212 case heap.PRE_HEAP: |
211 // reach.set(w,true); |
213 // reach.set(w,true); |
212 heap.push(w,oldvalue+length[e]); |
214 heap.push(w,oldvalue+length[e]); |
213 predecessor.set(w,e); |
215 predecessor.set(w,e); |
214 pred_node.set(w,v); |
216 pred_node.set(w,v); |
215 break; |
217 break; |
216 case Heap::IN_HEAP: |
218 case heap.IN_HEAP: |
217 if ( oldvalue+length[e] < heap[w] ) { |
219 if ( oldvalue+length[e] < heap[w] ) { |
218 heap.decrease(w, oldvalue+length[e]); |
220 heap.decrease(w, oldvalue+length[e]); |
219 predecessor.set(w,e); |
221 predecessor.set(w,e); |
220 pred_node.set(w,v); |
222 pred_node.set(w,v); |
221 } |
223 } |
222 break; |
224 break; |
223 case Heap::POST_HEAP: |
225 case heap.POST_HEAP: |
224 break; |
226 break; |
225 } |
227 } |
226 } |
228 } |
227 } |
229 } |
228 } |
230 } |