1 | /* |
---|
2 | *dijkstra |
---|
3 | *by jacint |
---|
4 | *Performs Dijkstra's algorithm from node s. |
---|
5 | * |
---|
6 | *Constructor: |
---|
7 | * |
---|
8 | *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance) |
---|
9 | * |
---|
10 | * |
---|
11 | * |
---|
12 | *Member functions: |
---|
13 | * |
---|
14 | *void run() |
---|
15 | * |
---|
16 | * The following function should be used after run() was already run. |
---|
17 | * |
---|
18 | * |
---|
19 | *T dist(node_iterator v) : returns the distance from s to v. |
---|
20 | * It is 0 if v is not reachable from s. |
---|
21 | * |
---|
22 | * |
---|
23 | *edge_iterator pred(node_iterator v) |
---|
24 | * Returns the last edge of a shortest s-v path. |
---|
25 | * Returns an invalid iterator if v=s or v is not |
---|
26 | * reachable from s. |
---|
27 | * |
---|
28 | * |
---|
29 | *bool reach(node_iterator v) : true if v is reachable from s |
---|
30 | * |
---|
31 | * |
---|
32 | * |
---|
33 | * |
---|
34 | * |
---|
35 | *Problems: |
---|
36 | * |
---|
37 | *Heap implementation is needed, because the priority queue of stl |
---|
38 | *does not have a mathod for key-decrease, so we had to use here a |
---|
39 | *g\'any solution. |
---|
40 | * |
---|
41 | *The implementation of infinity would be desirable, see after line 100. |
---|
42 | */ |
---|
43 | |
---|
44 | #ifndef DIJKSTRA_HH |
---|
45 | #define DIJKSTRA_HH |
---|
46 | |
---|
47 | #include <queue> |
---|
48 | #include <algorithm> |
---|
49 | |
---|
50 | #include <marci_graph_traits.hh> |
---|
51 | #include <marci_property_vector.hh> |
---|
52 | |
---|
53 | |
---|
54 | namespace std { |
---|
55 | namespace marci { |
---|
56 | |
---|
57 | |
---|
58 | |
---|
59 | |
---|
60 | |
---|
61 | template <typename graph_type, typename T> |
---|
62 | class dijkstra{ |
---|
63 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
---|
64 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
---|
65 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
---|
66 | typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; |
---|
67 | typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
---|
68 | |
---|
69 | |
---|
70 | graph_type& G; |
---|
71 | node_iterator s; |
---|
72 | node_property_vector<graph_type, edge_iterator> predecessor; |
---|
73 | node_property_vector<graph_type, T> distance; |
---|
74 | edge_property_vector<graph_type, T> length; |
---|
75 | node_property_vector<graph_type, bool> reached; |
---|
76 | |
---|
77 | public : |
---|
78 | |
---|
79 | /* |
---|
80 | The distance of all the nodes is 0. |
---|
81 | */ |
---|
82 | dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) : |
---|
83 | G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { } |
---|
84 | |
---|
85 | |
---|
86 | |
---|
87 | /*By Misi.*/ |
---|
88 | struct node_dist_comp |
---|
89 | { |
---|
90 | node_property_vector<graph_type, T> &d; |
---|
91 | node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {} |
---|
92 | |
---|
93 | bool operator()(const node_iterator& u, const node_iterator& v) const |
---|
94 | { return d.get(u) < d.get(v); } |
---|
95 | }; |
---|
96 | |
---|
97 | |
---|
98 | |
---|
99 | void run() { |
---|
100 | |
---|
101 | node_property_vector<graph_type, bool> scanned(G, false); |
---|
102 | std::priority_queue<node_iterator, vector<node_iterator>, node_dist_comp> |
---|
103 | heap(( node_dist_comp(distance) )); |
---|
104 | |
---|
105 | heap.push(s); |
---|
106 | reached.put(s, true); |
---|
107 | |
---|
108 | while (!heap.empty()) { |
---|
109 | |
---|
110 | node_iterator v=heap.top(); |
---|
111 | heap.pop(); |
---|
112 | |
---|
113 | |
---|
114 | if (!scanned.get(v)) { |
---|
115 | |
---|
116 | for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) { |
---|
117 | node_iterator w=G.head(e); |
---|
118 | |
---|
119 | if (!scanned.get(w)) { |
---|
120 | if (!reached.get(w)) { |
---|
121 | reached.put(w,true); |
---|
122 | distance.put(w, distance.get(v)-length.get(e)); |
---|
123 | predecessor.put(w,e); |
---|
124 | } else if (distance.get(v)-length.get(e)>distance.get(w)) { |
---|
125 | distance.put(w, distance.get(v)-length.get(e)); |
---|
126 | predecessor.put(w,e); |
---|
127 | } |
---|
128 | |
---|
129 | heap.push(w); |
---|
130 | |
---|
131 | } |
---|
132 | |
---|
133 | } |
---|
134 | scanned.put(v,true); |
---|
135 | |
---|
136 | } // if (!scanned.get(v)) |
---|
137 | |
---|
138 | |
---|
139 | |
---|
140 | } // while (!heap.empty()) |
---|
141 | |
---|
142 | |
---|
143 | } //void run() |
---|
144 | |
---|
145 | |
---|
146 | |
---|
147 | |
---|
148 | |
---|
149 | /* |
---|
150 | *Returns the distance of the node v. |
---|
151 | *It is 0 for the root and for the nodes not |
---|
152 | *reachable form the root. |
---|
153 | */ |
---|
154 | T dist(node_iterator v) { |
---|
155 | return -distance.get(v); |
---|
156 | } |
---|
157 | |
---|
158 | |
---|
159 | |
---|
160 | /* |
---|
161 | * Returns the last edge of a shortest s-v path. |
---|
162 | * Returns an invalid iterator if v=root or v is not |
---|
163 | * reachable from the root. |
---|
164 | */ |
---|
165 | edge_iterator pred(node_iterator v) { |
---|
166 | if (v!=s) { return predecessor.get(v);} |
---|
167 | else {return edge_iterator();} |
---|
168 | } |
---|
169 | |
---|
170 | |
---|
171 | |
---|
172 | bool reach(node_iterator v) { |
---|
173 | return reached.get(v); |
---|
174 | } |
---|
175 | |
---|
176 | |
---|
177 | |
---|
178 | |
---|
179 | |
---|
180 | |
---|
181 | |
---|
182 | |
---|
183 | |
---|
184 | };// class dijkstra |
---|
185 | |
---|
186 | |
---|
187 | |
---|
188 | } // namespace marci |
---|
189 | } |
---|
190 | #endif //DIJKSTRA_HH |
---|
191 | |
---|
192 | |
---|