]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <HTML> |
2 | <!-- | |
3 | Copyright (c) Michael Hansen 2009 | |
4 | ||
5 | Distributed under the Boost Software License, Version 1.0. | |
6 | (See accompanying file LICENSE_1_0.txt or copy at | |
7 | http://www.boost.org/LICENSE_1_0.txt) | |
8 | --> | |
9 | <Head> | |
10 | <Title>Boost Graph Library: Dijkstra's Shortest Paths (No Color Map)</Title> | |
11 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
12 | ALINK="#ff0000"> | |
13 | <IMG SRC="../../../boost.png" | |
14 | ALT="C++ Boost" width="277" height="86"> | |
15 | ||
16 | <BR Clear> | |
17 | ||
18 | <H1><A NAME="sec:dijkstra"></A> | |
19 | <TT>dijkstra_shortest_paths_no_color_map</TT> | |
20 | </H1> | |
21 | ||
22 | <P> | |
23 | <PRE> | |
24 | <i>// named parameter version</i> | |
25 | template <typename Graph, typename Param, typename Tag, typename Rest> | |
26 | void dijkstra_shortest_paths_no_color_map | |
27 | (const Graph& graph, | |
28 | typename graph_traits<Graph>::vertex_descriptor start_vertex, | |
29 | const bgl_named_params<Param,Tag,Rest>& params); | |
30 | ||
31 | <i>// non-named parameter version</i> | |
32 | template <typename Graph, typename <a href="DijkstraVisitor.html">DijkstraVisitor</a>, | |
33 | typename PredecessorMap, typename DistanceMap, | |
34 | typename WeightMap, typename VertexIndexMap, typename <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">DistanceCompare</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">DistanceWeightCombine</a>, | |
35 | typename DistanceInfinity, typename DistanceZero> | |
36 | void dijkstra_shortest_paths_no_color_map | |
37 | (const Graph& graph, | |
38 | typename graph_traits<Graph>::vertex_descriptor start_vertex, | |
39 | PredecessorMap predecessor_map, DistanceMap distance_map, WeightMap weight_map, | |
40 | VertexIndexMap index_map, | |
41 | DistanceCompare distance_compare, DistanceWeightCombine distance_weight_combine, | |
42 | DistanceInfinity distance_infinity, DistanceZero distance_zero); | |
43 | ||
44 | <i>// version that does not initialize the property maps</i> | |
45 | template <typename Graph, typename <a href="DijkstraVisitor.html">DijkstraVisitor</a>, | |
46 | typename PredecessorMap, typename DistanceMap, | |
47 | typename WeightMap, typename VertexIndexMap, typename <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">DistanceCompare</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">DistanceWeightCombine</a>, | |
48 | typename DistanceInfinity, typename DistanceZero> | |
49 | void dijkstra_shortest_paths_no_color_map_no_init | |
50 | (const Graph& graph, | |
51 | typename graph_traits<Graph>::vertex_descriptor start_vertex, | |
52 | PredecessorMap predecessor_map, DistanceMap distance_map, WeightMap weight_map, | |
53 | VertexIndexMap index_map, | |
54 | DistanceCompare distance_compare, DistanceWeightCombine distance_weight_combine, | |
55 | DistanceInfinity distance_infinity, DistanceZero distance_zero); | |
56 | </PRE> | |
57 | ||
58 | <P> | |
59 | This algorithm [<A HREF="bibliography.html#dijkstra59">10</A>,<A | |
60 | HREF="bibliography.html#clr90">8</A>] solves the single-source | |
61 | shortest-paths problem on a weighted, directed or undirected graph for | |
62 | the case where all edge weights are nonnegative. Use the Bellman-Ford | |
63 | algorithm for the case when some edge weights are negative. Use | |
64 | breadth-first search instead of Dijkstra's algorithm when all edge | |
65 | weights are equal to one. For the definition of the shortest-path | |
66 | problem see Section <A | |
67 | HREF="graph_theory_review.html#sec:shortest-paths-algorithms">Shortest-Paths | |
68 | Algorithms</A> for some background to the shortest-path problem. | |
69 | </P> | |
70 | ||
71 | <P> | |
72 | <tt>dijkstra_shortest_paths_no_color_map</tt> differs from the original <tt>dijkstra_shortest_paths</tt> algorithm by not using a color map to identify vertices as discovered or undiscovered. Instead, this is done with the distance map: a vertex <i>u</i> such that <i>distance_compare(distance_map[u], distance_infinity) == false</i> is considered to be undiscovered. Note that this means that edges with infinite weight will not work correctly in this algorithm. | |
73 | </P> | |
74 | ||
75 | <P> | |
76 | There are two main options for obtaining output from the | |
77 | <tt>dijkstra_shortest_paths_no_color_map()</tt> function. If you provide a | |
78 | distance property map through the <tt>distance_map()</tt> parameter | |
79 | then the shortest distance from the start vertex to every other | |
80 | vertex in the graph will be recorded in the distance map. Also you can | |
81 | record the shortest paths tree in a predecessor map: for each vertex | |
82 | <i>u in V</i>, <i>p[u]</i> will be the predecessor of <i>u</i> in | |
83 | the shortest paths tree (unless <i>p[u] = u</i>, in which case <i>u</i> is | |
84 | either the source or a vertex unreachable from the source). In | |
85 | addition to these two options, the user can provide their own | |
86 | custom-made visitor that takes actions during any of the | |
87 | algorithm's event points <a href="#4">[4]</a>.</P> | |
88 | ||
89 | <P> | |
90 | Dijkstra's algorithm finds all the shortest paths from the source | |
91 | vertex to every other vertex by iteratively "growing" the set of | |
92 | vertices <i>S</i> to which it knows the shortest path. At each step of | |
93 | the algorithm, the next vertex added to <i>S</i> is determined by a | |
94 | priority queue. The queue contains the vertices in <i>V - S</i><a | |
95 | href="#1">[1]</a> prioritized by their distance label, which is the | |
96 | length of the shortest path seen so far for each vertex. The vertex | |
97 | <i>u</i> at the top of the priority queue is then added to <i>S</i>, | |
98 | and each of its out-edges is relaxed: if the distance to <i>u</i> plus | |
99 | the weight of the out-edge <i>(u,v)</i> is less than the distance | |
100 | label for <i>v</i> then the estimated distance for vertex <i>v</i> is | |
101 | reduced. The algorithm then loops back, processing the next vertex at | |
102 | the top of the priority queue. The algorithm finishes when the | |
103 | priority queue is empty. | |
104 | </P> | |
105 | <p> | |
106 | The following is the pseudo-code for Dijkstra's single-source shortest | |
107 | paths algorithm. <i>w</i> is the edge weight, <i>d</i> is the distance label, | |
108 | and <i>p</i> is the predecessor of each vertex which is used to encode | |
109 | the shortest paths tree. <i>Q</i> is a priority queue that supports the | |
110 | DECREASE-KEY operation. The visitor event points for the algorithm are | |
111 | indicated by the labels on the right. | |
112 | </p> | |
113 | ||
114 | <table> | |
115 | <tr> | |
116 | <td valign="top"> | |
117 | <pre> | |
118 | DIJKSTRA(<i>G</i>, <i>s</i>, <i>w</i>) | |
119 | <i>d[s] := 0</i> | |
120 | INSERT(<i>Q</i>, <i>s</i>) | |
121 | <b>while</b> (<i>Q != Ø</i>) | |
122 | <i>u :=</i> EXTRACT-MIN(<i>Q</i>) | |
123 | <b>for</b> each vertex <i>v in Adj[u]</i> | |
124 | <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>) | |
125 | <i>d[v] := w(u,v) + d[u]</i> | |
126 | <i>p[v] := u</i> | |
127 | <b>if</b> (<i>d[v]</i> was originally infinity) | |
128 | INSERT(<i>Q</i>, <i>v</i>) | |
129 | <b>else</b> | |
130 | DECREASE-KEY(<i>Q</i>, <i>v</i>) | |
131 | <b>else</b> | |
132 | ... | |
133 | <b>end for</b> | |
134 | <b>end while</b> | |
135 | return (<i>d</i>, <i>p</i>) | |
136 | </pre> | |
137 | </td> | |
138 | <td valign="top"> | |
139 | <pre> | |
140 | ||
141 | ||
142 | discover vertex <i>s</i> | |
143 | ||
144 | examine vertex <i>u</i> | |
145 | examine edge <i>(u,v)</i> | |
146 | ||
147 | edge <i>(u,v)</i> relaxed | |
148 | ||
149 | ||
150 | discover vertex <i>v</i> | |
151 | ||
152 | ||
153 | edge <i>(u,v)</i> not relaxed | |
154 | ||
155 | finish vertex <i>u</i> | |
156 | </pre> | |
157 | </td> | |
158 | </tr> | |
159 | </table> | |
160 | ||
161 | <h3>Where Defined</h3> | |
162 | ||
163 | <a href="../../../boost/graph/dijkstra_shortest_paths_no_color_map.hpp"><tt>boost/graph/dijkstra_shortest_paths_no_color_map.hpp</tt></a> | |
164 | ||
165 | <h3>Parameters</h3> | |
166 | ||
167 | IN: <tt>const Graph& graph</tt> | |
168 | <blockquote> | |
169 | The graph object on which the algorithm will be applied. | |
170 | The type <tt>Graph</tt> must be a model of | |
171 | <a href="./VertexListGraph.html">Vertex List Graph</a> | |
172 | and <a href="./IncidenceGraph.html">Incidence Graph</a>.<br> | |
173 | </blockquote> | |
174 | ||
175 | IN: <tt>vertex_descriptor start_vertex</tt> | |
176 | <blockquote> | |
177 | The source vertex. All distance will be calculated from this vertex, | |
178 | and the shortest paths tree will be rooted at this vertex.<br> | |
179 | </blockquote> | |
180 | ||
181 | <h3>Named Parameters</h3> | |
182 | ||
183 | IN: <tt>weight_map(WeightMap weight_map)</tt> | |
184 | <blockquote> | |
185 | The weight or ``length'' of each edge in the graph. The weights | |
186 | must all be non-negative and non-infinite <a href="#3">[3]</a>. The algorithm will throw a | |
187 | <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a> | |
188 | exception is one of the edges is negative. | |
189 | The type <tt>WeightMap</tt> must be a model of | |
190 | <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of | |
191 | the graph needs to be usable as the key type for the weight | |
192 | map. The value type for this map must be | |
193 | the same as the value type of the distance map.<br> | |
194 | <b>Default:</b> <tt>get(edge_weight, graph)</tt><br> | |
195 | </blockquote> | |
196 | ||
197 | IN: <tt>index_map(VertexIndexMap index_map)</tt> | |
198 | <blockquote> | |
199 | This maps each vertex to an integer in the range <tt>[0, | |
200 | num_vertices(graph))</tt>. This is necessary for efficient updates of the | |
201 | heap data structure [<A | |
202 | HREF="bibliography.html#driscoll88">61</A>] when an edge is relaxed. | |
203 | The type | |
204 | <tt>VertexIndexMap</tt> must be a model of | |
205 | <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an | |
206 | integer type. The vertex descriptor type of the graph needs to be | |
207 | usable as the key type of the map.<br> | |
208 | <b>Default:</b> <tt>get(vertex_index, graph)</tt>. | |
209 | Note: if you use this default, make sure your graph has | |
210 | an internal <tt>vertex_index</tt> property. For example, | |
211 | <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does | |
212 | not have an internal <tt>vertex_index</tt> property. | |
213 | <br> | |
214 | </blockquote> | |
215 | ||
216 | OUT: <tt>predecessor_map(PredecessorMap predecessor_map)</tt> | |
217 | <blockquote> | |
218 | The predecessor map records the edges in the minimum spanning | |
219 | tree. Upon completion of the algorithm, the edges <i>(p[u],u)</i> | |
220 | for all <i>u in V</i> are in the minimum spanning tree. If <i>p[u] = | |
221 | u</i> then <i>u</i> is either the source vertex or a vertex that is | |
222 | not reachable from the source. The <tt>PredecessorMap</tt> type | |
223 | must be a <a | |
224 | href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write | |
225 | Property Map</a> whose key and value types are the same as the vertex | |
226 | descriptor type of the graph.<br> | |
227 | <b>Default:</b> <tt>dummy_property_map</tt><br> | |
228 | ||
229 | <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br> | |
230 | </blockquote> | |
231 | ||
232 | UTIL/OUT: <tt>distance_map(DistanceMap distance_map)</tt> | |
233 | <blockquote> | |
234 | The shortest path weight from the source vertex <tt>start_vertex</tt> to each | |
235 | vertex in the graph <tt>graph</tt> is recorded in this property map. The | |
236 | shortest path weight is the sum of the edge weights along the | |
237 | shortest path. The type <tt>DistanceMap</tt> must be a model of <a | |
238 | href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write | |
239 | Property Map</a>. The vertex descriptor type of the graph needs to | |
240 | be usable as the key type of the distance map. | |
241 | ||
242 | The value type of the distance map is the element type of a <a | |
243 | href="./Monoid.html">Monoid</a> formed with the <tt>distance_weight_combine</tt> | |
244 | function object and the <tt>distance_zero</tt> object for the identity | |
245 | element. Also the distance value type must have a <a | |
246 | href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"> | |
247 | StrictWeakOrdering</a> provided by the <tt>distance_compare</tt> function | |
248 | object.<br> | |
249 | <b>Default:</b> <a | |
250 | href="../../property_map/doc/iterator_property_map.html"> | |
251 | <tt>iterator_property_map</tt></a> created from a | |
252 | <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size | |
253 | <tt>num_vertices(graph)</tt> and using the <tt>index_map</tt> for the index | |
254 | map.<br> | |
255 | </blockquote> | |
256 | ||
257 | IN: <tt>distance_compare(CompareFunction distance_compare)</tt> | |
258 | <blockquote> | |
259 | This function is use to compare distances to determine which vertex | |
260 | is closer to the source vertex. The <tt>DistanceCompareFunction</tt> type | |
261 | must be a model of <a | |
262 | href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary | |
263 | Predicate</a> and have argument types that match the value type of | |
264 | the <tt>DistanceMap</tt> property map.<br> | |
265 | ||
266 | <b>Default:</b> | |
267 | <tt>std::less<D></tt> with <tt>D=typename | |
268 | property_traits<DistanceMap>::value_type</tt><br> | |
269 | </blockquote> | |
270 | ||
271 | IN: <tt>distance_combine(CombineFunction distance_weight_combine)</tt> | |
272 | <blockquote> | |
273 | This function is used to combine distances to compute the distance | |
274 | of a path. The <tt>DistanceWeightCombineFunction</tt> type must be a model of <a | |
275 | href="http://www.sgi.com/tech/stl/BinaryFunction.html">Binary | |
276 | Function</a>. The first argument type of the binary function must | |
277 | match the value type of the <tt>DistanceMap</tt> property map and | |
278 | the second argument type must match the value type of the | |
279 | <tt>WeightMap</tt> property map. The result type must be the same | |
280 | type as the distance value type.<br> | |
281 | ||
282 | <b>Default:</b> <tt>boost::closed_plus<D></tt> with | |
283 | <tt>D=typename property_traits<DistanceMap>::value_type</tt><br> | |
284 | </blockquote> | |
285 | ||
286 | IN: <tt>distance_inf(D distance_infinity)</tt> | |
287 | <blockquote> | |
288 | The <tt>distance_infinity</tt> object must be the greatest value of any <tt>D</tt> object. | |
289 | That is, <tt>distance_compare(d, distance_infinity) == true</tt> for any <tt>d != distance_infinity</tt>. | |
290 | The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>. All edges | |
291 | are assumed to have weight less than (by <tt>distance_compare</tt>) this | |
292 | value.<br> | |
293 | <b>Default:</b> <tt>std::numeric_limits<D>::max()</tt><br> | |
294 | </blockquote> | |
295 | ||
296 | IN: <tt>distance_zero(D distance_zero)</tt> | |
297 | <blockquote> | |
298 | The <tt>distance_zero</tt> value must be the identity element for the | |
299 | <a href="./Monoid.html">Monoid</a> formed by the distance values | |
300 | and the <tt>distance_weight_combine</tt> function object. | |
301 | The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br> | |
302 | <b>Default:</b> <tt>D()</tt>with | |
303 | <tt>D=typename property_traits<DistanceMap>::value_type</tt><br> | |
304 | </blockquote> | |
305 | ||
306 | OUT: <tt>visitor(DijkstraVisitor v)</tt> | |
307 | <blockquote> | |
308 | Use this to specify actions that you would like to happen | |
309 | during certain event points within the algorithm. | |
310 | The type <tt>DijkstraVisitor</tt> must be a model of the | |
311 | <a href="./DijkstraVisitor.html">Dijkstra Visitor</a> concept. | |
312 | The visitor object is passed by value <a | |
313 | href="#2">[2]</a>.<br> | |
314 | <b>Default:</b> <tt>dijkstra_visitor<null_visitor></tt><br> | |
315 | </blockquote> | |
316 | ||
317 | ||
318 | <H3>Complexity</H3> | |
319 | ||
320 | <P> | |
321 | The time complexity is <i>O(V log V + E)</i>. | |
322 | ||
323 | ||
324 | <h3>Visitor Event Points</h3> | |
325 | ||
326 | <ul> | |
327 | <li><b><tt>vis.initialize_vertex(u, g)</tt></b> | |
328 | is invoked on each vertex in the graph before the start of the | |
329 | algorithm. | |
330 | <li><b><tt>vis.examine_vertex(u, g)</tt></b> | |
331 | is invoked on a vertex as it is removed from the priority queue | |
332 | and added to set <i>S</i>. At this point we know that <i>(p[u],u)</i> | |
333 | is a shortest-paths tree edge so | |
334 | <i>d[u] = delta(s,u) = d[p[u]] + w(p[u],u)</i>. Also, the distances | |
335 | of the examined vertices is monotonically increasing | |
336 | <i>d[u<sub>1</sub>] <= d[u<sub>2</sub>] <= d[u<sub>n</sub>]</i>. | |
337 | <li><b><tt>vis.examine_edge(e, g)</tt></b> | |
338 | is invoked on each out-edge of a vertex immediately after it has | |
339 | been added to set <i>S</i>. | |
340 | <li><b><tt>vis.edge_relaxed(e, g)</tt></b> | |
341 | is invoked on edge <i>(u,v)</i> if <i>d[u] + w(u,v) < d[v]</i>. | |
342 | The edge <i>(u,v)</i> that participated in the last | |
343 | relaxation for vertex <i>v</i> is an edge in the shortest paths tree. | |
344 | <li><b><tt>vis.discover_vertex(v, g)</tt></b> | |
345 | is invoked on vertex <i>v</i> when the edge | |
346 | <i>(u,v)</i> is examined and <i>v</i> has not yet been discovered (i.e. its distance was infinity before relaxation was attempted on the edge). This | |
347 | is also when the vertex is inserted into the priority queue. | |
348 | <li><b><tt>vis.edge_not_relaxed(e, g)</tt></b> | |
349 | is invoked if the edge is not relaxed (see above). | |
350 | <li><b><tt>vis.finish_vertex(u, g)</tt></b> | |
351 | is invoked on a vertex after all of its out edges have | |
352 | been examined. | |
353 | </ul> | |
354 | ||
355 | <H3>Example</H3> | |
356 | ||
357 | <P> | |
358 | See <a href="../example/dijkstra-no-color-map-example.cpp"> | |
359 | <TT>example/dijkstra-no-color-map-example.cpp</TT></a> for an example of using Dijkstra's algorithm. | |
360 | ||
361 | <H3>See also</H3> <a href="dijkstra_shortest_paths.html">dijkstra_shortest_paths</a> for a version of dijkstra's shortest path that uses a color map. | |
362 | ||
363 | <H3>Notes</H3> | |
364 | ||
365 | <p>Based on the documentation for <a href="dijkstra_shortest_paths.html">dijkstra_shortest_paths</a>. | |
366 | ||
367 | <p><a name="1">[1]</a> | |
368 | The algorithm used here saves a little space by not putting all <i>V - | |
369 | S</i> vertices in the priority queue at once, but instead only those | |
370 | vertices in <i>V - S</i> that are discovered and therefore have a | |
371 | distance less than infinity. | |
372 | ||
373 | <p><a name="2">[2]</a> | |
374 | Since the visitor parameter is passed by value, if your visitor | |
375 | contains state then any changes to the state during the algorithm | |
376 | will be made to a copy of the visitor object, not the visitor object | |
377 | passed in. Therefore you may want the visitor to hold this state by | |
378 | pointer or reference. | |
379 | ||
380 | <p><a name="3">[3]</a> | |
381 | The algorithm will not work correctly if any of the edge weights are equal to infinity since the infinite distance value is used to determine if a vertex has been discovered. | |
382 | ||
383 | <p><a name="4">[4]</a> | |
384 | Calls to the visitor events occur in the same order as <tt>dijkstra_shortest_paths</tt> (i.e. <i>discover_vertex(u)</i> will always be called after <i>examine_vertex(u)</i> for an undiscovered vertex <i>u</i>). However, the vertices of the graph given to <i>dijkstra_shortest_paths_no_color_map</i> will <b>not</b> necessarily be visited in the same order as <i>dijkstra_shortest_paths</i>. | |
385 | ||
386 | <br> | |
387 | <HR> | |
388 | <TABLE> | |
389 | <TR valign=top> | |
390 | <TD nowrap>Copyright © 2009</TD><TD> | |
391 | Trustees of Indiana University</TD></TR></TABLE> | |
392 | ||
393 | </BODY> | |
394 | </HTML> |