43 typename LengthMap, |
43 typename LengthMap, |
44 typename Heap> |
44 typename Heap> |
45 #else |
45 #else |
46 template <typename Graph, |
46 template <typename Graph, |
47 typename LengthMap=typename Graph::template EdgeMap<int>, |
47 typename LengthMap=typename Graph::template EdgeMap<int>, |
48 template <class,class,class> class Heap = BinHeap > |
48 template <class,class,class,class> class Heap = BinHeap > |
49 #endif |
49 #endif |
50 class Dijkstra{ |
50 class Dijkstra{ |
51 public: |
51 public: |
52 typedef typename Graph::Node Node; |
52 typedef typename Graph::Node Node; |
53 typedef typename Graph::NodeIt NodeIt; |
53 typedef typename Graph::NodeIt NodeIt; |
144 ///compute the |
144 ///compute the |
145 ///shortest path to each node. The algorithm computes |
145 ///shortest path to each node. The algorithm computes |
146 ///- The shortest path tree. |
146 ///- The shortest path tree. |
147 ///- The distance of each node from the root. |
147 ///- The distance of each node from the root. |
148 template <typename Graph, typename LengthMap, |
148 template <typename Graph, typename LengthMap, |
149 template<class,class,class> class Heap > |
149 template<class,class,class,class> class Heap > |
150 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
150 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
151 |
151 |
152 NodeIt u; |
152 NodeIt u; |
153 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
153 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
154 predecessor.set(u,INVALID); |
154 predecessor.set(u,INVALID); |
155 pred_node.set(u,INVALID); |
155 pred_node.set(u,INVALID); |
156 } |
156 } |
157 |
157 |
158 typename Graph::template NodeMap<int> heap_map(G,-1); |
158 typename Graph::template NodeMap<int> heap_map(G,-1); |
159 |
159 |
160 Heap<Node, ValueType, typename Graph::template NodeMap<int> > |
160 typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>, |
161 heap(heap_map); |
161 std::less<ValueType> > |
|
162 HeapType; |
|
163 |
|
164 HeapType heap(heap_map); |
162 |
165 |
163 heap.push(s,0); |
166 heap.push(s,0); |
164 |
167 |
165 while ( !heap.empty() ) { |
168 while ( !heap.empty() ) { |
166 |
169 |
174 for(G.first(e, v); |
177 for(G.first(e, v); |
175 G.valid(e); G.next(e)) { |
178 G.valid(e); G.next(e)) { |
176 Node w=G.bNode(e); |
179 Node w=G.bNode(e); |
177 |
180 |
178 switch(heap.state(w)) { |
181 switch(heap.state(w)) { |
179 case heap.PRE_HEAP: |
182 case HeapType::PRE_HEAP: |
180 heap.push(w,oldvalue+length[e]); |
183 heap.push(w,oldvalue+length[e]); |
181 predecessor.set(w,e); |
184 predecessor.set(w,e); |
182 pred_node.set(w,v); |
185 pred_node.set(w,v); |
183 break; |
186 break; |
184 case heap.IN_HEAP: |
187 case HeapType::IN_HEAP: |
185 if ( oldvalue+length[e] < heap[w] ) { |
188 if ( oldvalue+length[e] < heap[w] ) { |
186 heap.decrease(w, oldvalue+length[e]); |
189 heap.decrease(w, oldvalue+length[e]); |
187 predecessor.set(w,e); |
190 predecessor.set(w,e); |
188 pred_node.set(w,v); |
191 pred_node.set(w,v); |
189 } |
192 } |
190 break; |
193 break; |
191 case heap.POST_HEAP: |
194 case HeapType::POST_HEAP: |
192 break; |
195 break; |
193 } |
196 } |
194 } |
197 } |
195 } //FIXME tis bracket |
198 } //FIXME tis bracket |
196 } |
199 } |