41 template <typename Graph, |
41 template <typename Graph, |
42 typename LengthMap, |
42 typename LengthMap, |
43 typename Heap> |
43 typename Heap> |
44 #else |
44 #else |
45 template <typename Graph, |
45 template <typename Graph, |
46 typename LengthMap=typename Graph::EdgeMap<int>, |
46 typename LengthMap=typename Graph::template EdgeMap<int>, |
47 template <class,class,class> class Heap = BinHeap > |
47 template <class,class,class> class Heap = BinHeap > |
48 #endif |
48 #endif |
49 class Dijkstra{ |
49 class Dijkstra{ |
50 public: |
50 public: |
51 typedef typename Graph::Node Node; |
51 typedef typename Graph::Node Node; |
52 typedef typename Graph::NodeIt NodeIt; |
52 typedef typename Graph::NodeIt NodeIt; |
53 typedef typename Graph::Edge Edge; |
53 typedef typename Graph::Edge Edge; |
54 typedef typename Graph::OutEdgeIt OutEdgeIt; |
54 typedef typename Graph::OutEdgeIt OutEdgeIt; |
55 |
55 |
56 typedef typename LengthMap::ValueType ValueType; |
56 typedef typename LengthMap::ValueType ValueType; |
57 typedef typename Graph::NodeMap<Edge> PredMap; |
57 typedef typename Graph::template NodeMap<Edge> PredMap; |
58 typedef typename Graph::NodeMap<Node> PredNodeMap; |
58 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
59 typedef typename Graph::NodeMap<ValueType> DistMap; |
59 typedef typename Graph::template NodeMap<ValueType> DistMap; |
60 |
60 |
61 private: |
61 private: |
62 const Graph& G; |
62 const Graph& G; |
63 const LengthMap& length; |
63 const LengthMap& length; |
64 PredMap predecessor; |
64 PredMap predecessor; |
152 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
152 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
153 predecessor.set(u,INVALID); |
153 predecessor.set(u,INVALID); |
154 pred_node.set(u,INVALID); |
154 pred_node.set(u,INVALID); |
155 } |
155 } |
156 |
156 |
157 typename Graph::NodeMap<int> heap_map(G,-1); |
157 typename Graph::template NodeMap<int> heap_map(G,-1); |
158 |
158 |
159 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); |
159 Heap<Node, ValueType, typename Graph::template NodeMap<int> > |
|
160 heap(heap_map); |
160 |
161 |
161 heap.push(s,0); |
162 heap.push(s,0); |
162 |
163 |
163 while ( !heap.empty() ) { |
164 while ( !heap.empty() ) { |
164 |
165 |