equal
deleted
inserted
replaced
43 |
43 |
44 const Graph& G; |
44 const Graph& G; |
45 const LengthMap& length; |
45 const LengthMap& length; |
46 typename Graph::NodeMap<Edge> predecessor; |
46 typename Graph::NodeMap<Edge> predecessor; |
47 typename Graph::NodeMap<T> distance; |
47 typename Graph::NodeMap<T> distance; |
|
48 //FIXME: |
48 typename Graph::NodeMap<bool> reach; |
49 typename Graph::NodeMap<bool> reach; |
|
50 //typename Graph::NodeMap<int> reach; |
49 |
51 |
50 public : |
52 public : |
51 |
53 |
52 /* |
54 /* |
53 The distance of the nodes is 0. |
55 The distance of the nodes is 0. |
63 predecessor.set(u,INVALID); |
65 predecessor.set(u,INVALID); |
64 distance.set(u,0); |
66 distance.set(u,0); |
65 reach.set(u,false); |
67 reach.set(u,false); |
66 } |
68 } |
67 |
69 |
|
70 //FIXME: |
68 typename Graph::NodeMap<bool> scanned(G,false); |
71 typename Graph::NodeMap<bool> scanned(G,false); |
|
72 //typename Graph::NodeMap<int> scanned(G,false); |
69 typename Graph::NodeMap<int> heap_map(G,-1); |
73 typename Graph::NodeMap<int> heap_map(G,-1); |
70 |
74 |
71 Heap heap(heap_map); |
75 Heap heap(heap_map); |
72 |
76 |
73 heap.push(s,0); |
77 heap.push(s,0); |
74 reach.set(s, true); |
78 reach.set(s, true); |
75 |
79 |
76 while ( !heap.empty() ) { |
80 while ( !heap.empty() ) { |
77 |
81 |
78 Node v=heap.top(); |
82 Node v=heap.top(); |
79 T oldvalue=heap.get(v); |
83 T oldvalue=heap[v]; |
80 heap.pop(); |
84 heap.pop(); |
81 distance.set(v, oldvalue); |
85 distance.set(v, oldvalue); |
82 scanned.set(v,true); |
86 scanned.set(v,true); |
83 |
87 |
84 OutEdgeIt e; |
88 OutEdgeIt e; |
88 if ( !scanned[w] ) { |
92 if ( !scanned[w] ) { |
89 if ( !reach[w] ) { |
93 if ( !reach[w] ) { |
90 reach.set(w,true); |
94 reach.set(w,true); |
91 heap.push(w,oldvalue+length[e]); |
95 heap.push(w,oldvalue+length[e]); |
92 predecessor.set(w,e); |
96 predecessor.set(w,e); |
93 } else if ( oldvalue+length[e] < heap.get(w) ) { |
97 } else if ( oldvalue+length[e] < heap[w] ) { |
94 predecessor.set(w,e); |
98 predecessor.set(w,e); |
95 heap.decrease(w, oldvalue+length[e]); |
99 heap.decrease(w, oldvalue+length[e]); |
96 } |
100 } |
97 } |
101 } |
98 } |
102 } |
99 } |
103 } |
100 } |
104 } |
101 |
105 |
102 |
|
103 T dist(Node v) { |
106 T dist(Node v) { |
104 return distance[v]; |
107 return distance[v]; |
105 } |
108 } |
106 |
|
107 |
109 |
108 Edge pred(Node v) { |
110 Edge pred(Node v) { |
109 return predecessor[v]; |
111 return predecessor[v]; |
110 } |
112 } |
111 |
113 |
112 |
|
113 bool reached(Node v) { |
114 bool reached(Node v) { |
114 return reach[v]; |
115 return reach[v]; |
115 } |
116 } |
116 |
117 |
117 }; |
118 }; |