1 /* |
1 /* |
2 *dijkstra |
2 *dijkstra |
3 *by jacint |
3 *by jacint |
4 *Performs Dijkstra's algorithm from node s. |
4 *Performs Dijkstra's algorithm from Node s. |
5 * |
5 * |
6 *Constructor: |
6 *Constructor: |
7 * |
7 * |
8 *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance) |
8 *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance) |
9 * |
9 * |
10 * |
10 * |
11 * |
11 * |
12 *Member functions: |
12 *Member functions: |
13 * |
13 * |
14 *void run() |
14 *void run() |
15 * |
15 * |
16 * The following function should be used after run() was already run. |
16 * The following function should be used after run() was already run. |
17 * |
17 * |
18 * |
18 * |
19 *T dist(node_iterator v) : returns the distance from s to v. |
19 *T dist(NodeIt v) : returns the distance from s to v. |
20 * It is 0 if v is not reachable from s. |
20 * It is 0 if v is not reachable from s. |
21 * |
21 * |
22 * |
22 * |
23 *edge_iterator pred(node_iterator v) |
23 *EdgeIt pred(NodeIt v) |
24 * Returns the last edge of a shortest s-v path. |
24 * Returns the last Edge of a shortest s-v path. |
25 * Returns an invalid iterator if v=s or v is not |
25 * Returns an invalid iterator if v=s or v is not |
26 * reachable from s. |
26 * reachable from s. |
27 * |
27 * |
28 * |
28 * |
29 *bool reach(node_iterator v) : true if v is reachable from s |
29 *bool reach(NodeIt v) : true if v is reachable from s |
30 * |
30 * |
31 * |
31 * |
32 * |
32 * |
33 * |
33 * |
34 * |
34 * |
58 |
58 |
59 |
59 |
60 |
60 |
61 template <typename graph_type, typename T> |
61 template <typename graph_type, typename T> |
62 class dijkstra{ |
62 class dijkstra{ |
63 typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
63 typedef typename graph_traits<graph_type>::NodeIt NodeIt; |
64 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
64 typedef typename graph_traits<graph_type>::EdgeIt EdgeIt; |
65 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
65 typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt; |
66 typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; |
66 typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt; |
67 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
67 typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt; |
68 |
68 |
69 |
69 |
70 graph_type& G; |
70 graph_type& G; |
71 node_iterator s; |
71 NodeIt s; |
72 node_property_vector<graph_type, edge_iterator> predecessor; |
72 NodeMap<graph_type, EdgeIt> predecessor; |
73 node_property_vector<graph_type, T> distance; |
73 NodeMap<graph_type, T> distance; |
74 edge_property_vector<graph_type, T> length; |
74 EdgeMap<graph_type, T> length; |
75 node_property_vector<graph_type, bool> reached; |
75 NodeMap<graph_type, bool> reached; |
76 |
76 |
77 public : |
77 public : |
78 |
78 |
79 /* |
79 /* |
80 The distance of all the nodes is 0. |
80 The distance of all the Nodes is 0. |
81 */ |
81 */ |
82 dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) : |
82 dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) : |
83 G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { } |
83 G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { } |
84 |
84 |
85 |
85 |
86 |
86 |
87 /*By Misi.*/ |
87 /*By Misi.*/ |
88 struct node_dist_comp |
88 struct Node_dist_comp |
89 { |
89 { |
90 node_property_vector<graph_type, T> &d; |
90 NodeMap<graph_type, T> &d; |
91 node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {} |
91 Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} |
92 |
92 |
93 bool operator()(const node_iterator& u, const node_iterator& v) const |
93 bool operator()(const NodeIt& u, const NodeIt& v) const |
94 { return d.get(u) < d.get(v); } |
94 { return d.get(u) < d.get(v); } |
95 }; |
95 }; |
96 |
96 |
97 |
97 |
98 |
98 |
99 void run() { |
99 void run() { |
100 |
100 |
101 node_property_vector<graph_type, bool> scanned(G, false); |
101 NodeMap<graph_type, bool> scanned(G, false); |
102 std::priority_queue<node_iterator, vector<node_iterator>, node_dist_comp> |
102 std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> |
103 heap(( node_dist_comp(distance) )); |
103 heap(( Node_dist_comp(distance) )); |
104 |
104 |
105 heap.push(s); |
105 heap.push(s); |
106 reached.put(s, true); |
106 reached.put(s, true); |
107 |
107 |
108 while (!heap.empty()) { |
108 while (!heap.empty()) { |
109 |
109 |
110 node_iterator v=heap.top(); |
110 NodeIt v=heap.top(); |
111 heap.pop(); |
111 heap.pop(); |
112 |
112 |
113 |
113 |
114 if (!scanned.get(v)) { |
114 if (!scanned.get(v)) { |
115 |
115 |
116 for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) { |
116 for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) { |
117 node_iterator w=G.head(e); |
117 NodeIt w=G.head(e); |
118 |
118 |
119 if (!scanned.get(w)) { |
119 if (!scanned.get(w)) { |
120 if (!reached.get(w)) { |
120 if (!reached.get(w)) { |
121 reached.put(w,true); |
121 reached.put(w,true); |
122 distance.put(w, distance.get(v)-length.get(e)); |
122 distance.put(w, distance.get(v)-length.get(e)); |
145 |
145 |
146 |
146 |
147 |
147 |
148 |
148 |
149 /* |
149 /* |
150 *Returns the distance of the node v. |
150 *Returns the distance of the Node v. |
151 *It is 0 for the root and for the nodes not |
151 *It is 0 for the root and for the Nodes not |
152 *reachable form the root. |
152 *reachable form the root. |
153 */ |
153 */ |
154 T dist(node_iterator v) { |
154 T dist(NodeIt v) { |
155 return -distance.get(v); |
155 return -distance.get(v); |
156 } |
156 } |
157 |
157 |
158 |
158 |
159 |
159 |
160 /* |
160 /* |
161 * Returns the last edge of a shortest s-v path. |
161 * Returns the last Edge of a shortest s-v path. |
162 * Returns an invalid iterator if v=root or v is not |
162 * Returns an invalid iterator if v=root or v is not |
163 * reachable from the root. |
163 * reachable from the root. |
164 */ |
164 */ |
165 edge_iterator pred(node_iterator v) { |
165 EdgeIt pred(NodeIt v) { |
166 if (v!=s) { return predecessor.get(v);} |
166 if (v!=s) { return predecessor.get(v);} |
167 else {return edge_iterator();} |
167 else {return EdgeIt();} |
168 } |
168 } |
169 |
169 |
170 |
170 |
171 |
171 |
172 bool reach(node_iterator v) { |
172 bool reach(NodeIt v) { |
173 return reached.get(v); |
173 return reached.get(v); |
174 } |
174 } |
175 |
175 |
176 |
176 |
177 |
177 |