equal
deleted
inserted
replaced
1 // -*- C++ -*- |
1 // -*- C++ -*- |
2 /* |
2 /* |
3 *template <Graph, T, Heap=FibHeap> |
3 *template <Graph, T, Heap=FibHeap> |
4 * |
4 * |
5 * |
|
6 *Constructor: |
5 *Constructor: |
7 * |
6 * |
8 *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length) |
7 *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length) |
9 * |
|
10 * |
8 * |
11 * |
9 * |
12 *Member functions: |
10 *Member functions: |
13 * |
11 * |
14 *void run() |
12 *void run() |
15 * |
13 * |
16 * The following function should be used after run() was already run. |
14 * The following function should be used after run() was already run. |
17 * |
15 * |
18 * |
|
19 *T dist(NodeIt v) : returns the distance from s to v. |
16 *T dist(NodeIt v) : returns the distance from s to v. |
20 * It is 0 if v is not reachable from s. |
17 * It is 0 if v is not reachable from s. |
21 * |
|
22 * |
18 * |
23 *EdgeIt pred(NodeIt v) : returns the last edge |
19 *EdgeIt pred(NodeIt v) : returns the last edge |
24 * of a shortest s-v path. Returns an invalid iterator |
20 * of a shortest s-v path. Returns an invalid iterator |
25 * if v=s or v is not reachable from s. |
21 * if v=s or v is not reachable from s. |
26 * |
|
27 * |
22 * |
28 *bool reach(NodeIt v) : true iff v is reachable from s |
23 *bool reach(NodeIt v) : true iff v is reachable from s |
29 * |
24 * |
30 */ |
25 */ |
31 |
26 |
74 |
69 |
75 while ( !heap.empty() ) { |
70 while ( !heap.empty() ) { |
76 |
71 |
77 NodeIt v=heap.top(); |
72 NodeIt v=heap.top(); |
78 T oldvalue=heap.get(v); |
73 T oldvalue=heap.get(v); |
|
74 heap.pop(); |
79 distance.set(v, oldvalue); |
75 distance.set(v, oldvalue); |
80 heap.pop(); |
76 |
81 |
|
82 OutEdgeIt e; |
77 OutEdgeIt e; |
83 for( G.getFirst(e,v); G.valid(e); G.next(e)) { |
78 for( G.getFirst(e,v); G.valid(e); G.next(e)) { |
84 NodeIt w=G.bNode(e); |
79 NodeIt w=G.bNode(e); |
85 |
80 |
86 if ( !scanned.get(w) ) { |
81 if ( !scanned.get(w) ) { |
87 if ( !reached.get(w) ) { |
82 if ( !reached.get(w) ) { |
88 reached.set(w,true); |
83 reached.set(w,true); |
89 heap.push(w,oldvalue+length.get(e)); |
84 heap.push(w,oldvalue+length.get(e)); |
90 predecessor.set(w,e); |
85 predecessor.set(w,e); |
91 |
|
92 } else if ( oldvalue+length.get(e) < heap.get(w) ) { |
86 } else if ( oldvalue+length.get(e) < heap.get(w) ) { |
93 predecessor.set(w,e); |
87 predecessor.set(w,e); |
94 heap.decrease(w, oldvalue+length.get(e)); |
88 heap.decrease(w, oldvalue+length.get(e)); |
95 } |
89 } |
96 } |
90 } |
112 |
106 |
113 |
107 |
114 bool reach(NodeIt v) { |
108 bool reach(NodeIt v) { |
115 return reached.get(v); |
109 return reached.get(v); |
116 } |
110 } |
117 |
111 |
118 }; |
112 }; |
119 |
113 |
120 } |
114 } |
121 |
115 |
122 #endif |
116 #endif |
123 |
117 |
124 |
118 |