1 // -*- C++ -*- |
1 // -*- C++ -*- |
2 |
|
3 //ha predecessor az elejen nem invalid, akkor hagyd csak ugy |
|
4 //scanned mutatja hogy jo ertek van-e benne vagy szemet |
|
5 |
|
6 /* |
2 /* |
7 *template <Graph, T, Heap=FibHeap> |
3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> > |
8 * |
4 * |
9 *Constructor: |
5 *Constructor: |
10 * |
6 * |
11 *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length) |
7 *Dijkstra(Graph G, LengthMap length) |
12 * |
8 * |
13 * |
9 * |
14 *Member functions: |
10 *Methods: |
15 * |
11 * |
16 *void run() |
12 *void run(Node s) |
17 * |
13 * |
18 * The following function should be used after run() was already run. |
14 *T dist(Node v) : After run(s) was run, it returns the distance from s to v. |
|
15 * Returns T() if v is not reachable from s. |
19 * |
16 * |
20 *T dist(NodeIt v) : returns the distance from s to v. |
17 *Edge pred(Node v) : After run(s) was run, it returns the last |
21 * It is 0 if v is not reachable from s. |
18 * edge of a shortest s-v path. It is INVALID for s and for |
|
19 * the nodes not reachable from s. |
22 * |
20 * |
23 *EdgeIt pred(NodeIt v) : returns the last edge |
21 *bool reached(Node v) : After run(s) was run, it is true iff v is |
24 * of a shortest s-v path. Returns an invalid iterator |
22 * reachable from s |
25 * if v=s or v is not reachable from s. |
|
26 * |
|
27 *bool reach(NodeIt v) : true iff v is reachable from s |
|
28 * |
23 * |
29 */ |
24 */ |
30 |
25 |
31 #ifndef DIJKSTRA_H |
26 #ifndef HUGO_DIJKSTRA_H |
32 #define DIJKSTRA_H |
27 #define HUGO_DIJKSTRA_H |
33 |
28 |
34 #include <fib_heap.h> |
29 #include <fib_heap.h> |
|
30 #include <invalid.h> |
35 |
31 |
36 namespace hugo { |
32 namespace hugo { |
37 |
33 |
38 template <typename Graph, typename T, |
34 template <typename Graph, typename T, |
39 typename Heap=FibHeap<typename Graph::NodeIt, T, |
35 typename Heap=FibHeap<typename Graph::Node, T, |
40 typename Graph::NodeMap<int> > > |
36 typename Graph::NodeMap<int> >, |
41 class Dijkstra{ |
37 typename LengthMap=typename Graph::EdgeMap<T> > |
42 typedef typename Graph::NodeIt NodeIt; |
38 class Dijkstra{ |
43 typedef typename Graph::EdgeIt EdgeIt; |
39 typedef typename Graph::Node Node; |
44 typedef typename Graph::OutEdgeIt OutEdgeIt; |
40 typedef typename Graph::NodeIt NodeIt; |
45 |
41 typedef typename Graph::Edge Edge; |
46 Graph& G; |
42 typedef typename Graph::OutEdgeIt OutEdgeIt; |
47 NodeIt s; |
43 |
48 typename Graph::NodeMap<EdgeIt> predecessor; |
44 const Graph& G; |
49 typename Graph::NodeMap<T> distance; |
45 const LengthMap& length; |
50 typename Graph::EdgeMap<T>& length; |
46 typename Graph::NodeMap<Edge> predecessor; |
51 typename Graph::NodeMap<bool> reached; |
47 typename Graph::NodeMap<T> distance; |
52 |
48 typename Graph::NodeMap<bool> reach; |
|
49 |
53 public : |
50 public : |
54 |
51 |
55 /* |
52 /* |
56 The distance of the nodes is 0. |
53 The distance of the nodes is 0. |
57 */ |
54 */ |
58 Dijkstra(Graph& _G, NodeIt const _s, |
55 Dijkstra(Graph& _G, LengthMap& _length) : G(_G), |
59 typename Graph::EdgeMap<T>& _length) : |
56 length(_length), predecessor(_G), distance(_G), reach(_G) { } |
60 G(_G), s(_s), predecessor(G), distance(G), |
|
61 length(_length), reached(G, false) { } |
|
62 |
57 |
|
58 |
|
59 void run(Node s) { |
63 |
60 |
64 void run() { |
61 NodeIt u; |
|
62 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
|
63 predecessor.set(u,INVALID); |
|
64 distance.set(u,0); |
|
65 reach.set(u,false); |
|
66 } |
|
67 |
|
68 typename Graph::NodeMap<bool> scanned(G,false); |
|
69 typename Graph::NodeMap<int> heap_map(G,-1); |
|
70 |
|
71 Heap heap(heap_map); |
|
72 |
|
73 heap.push(s,0); |
|
74 reach.set(s, true); |
|
75 |
|
76 while ( !heap.empty() ) { |
65 |
77 |
66 typename Graph::NodeMap<bool> scanned(G, false); |
78 Node v=heap.top(); |
67 typename Graph::NodeMap<int> heap_map(G,-1); |
79 T oldvalue=heap.get(v); |
|
80 heap.pop(); |
|
81 distance.set(v, oldvalue); |
|
82 scanned.set(v,true); |
68 |
83 |
69 Heap heap(heap_map); |
84 OutEdgeIt e; |
70 |
85 for( G.first(e,v); G.valid(e); G.next(e)) { |
71 heap.push(s,0); |
86 Node w=G.head(e); |
72 reached.set(s, true); |
|
73 |
|
74 while ( !heap.empty() ) { |
|
75 |
|
76 NodeIt v=heap.top(); |
|
77 T oldvalue=heap.get(v); |
|
78 heap.pop(); |
|
79 distance.set(v, oldvalue); |
|
80 scanned.set(v,true); |
|
81 |
|
82 OutEdgeIt e; |
|
83 for( G.getFirst(e,v); G.valid(e); G.next(e)) { |
|
84 NodeIt w=G.bNode(e); |
|
85 |
87 |
86 if ( !scanned.get(w) ) { |
88 if ( !scanned[w] ) { |
87 if ( !reached.get(w) ) { |
89 if ( !reach[w] ) { |
88 reached.set(w,true); |
90 reach.set(w,true); |
89 heap.push(w,oldvalue+length.get(e)); |
91 heap.push(w,oldvalue+length[e]); |
90 predecessor.set(w,e); |
92 predecessor.set(w,e); |
91 } else if ( oldvalue+length.get(e) < heap.get(w) ) { |
93 } else if ( oldvalue+length[e] < heap.get(w) ) { |
92 predecessor.set(w,e); |
94 predecessor.set(w,e); |
93 heap.decrease(w, oldvalue+length.get(e)); |
95 heap.decrease(w, oldvalue+length[e]); |
94 } |
|
95 } |
96 } |
96 } |
97 } |
97 } |
98 } |
98 } |
99 } |
99 |
100 } |
|
101 |
100 |
102 |
101 T dist(NodeIt v) { |
103 T dist(Node v) { |
102 return distance.get(v); |
104 return distance[v]; |
103 } |
105 } |
104 |
106 |
105 |
107 |
106 EdgeIt pred(NodeIt v) { |
108 Edge pred(Node v) { |
107 if ( v!=s ) return predecessor.get(v); |
109 return predecessor[v]; |
108 else return EdgeIt(); |
110 } |
109 } |
|
110 |
111 |
111 |
112 |
112 bool reach(NodeIt v) { |
113 bool reached(Node v) { |
113 return reached.get(v); |
114 return reach[v]; |
114 } |
115 } |
115 |
116 |
116 }; |
117 }; |
117 |
118 |
118 } |
119 } |
119 |
120 |
120 #endif |
121 #endif |
121 |
122 |