1 .. Copyright (C) 2004-2008 The Trustees of Indiana University.
2 Use, modification and distribution is subject to the Boost Software
3 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
4 http://www.boost.org/LICENSE_1_0.txt)
6 ==============================================
7 |Logo| Dijkstra's Single-Source Shortest Paths
8 ==============================================
12 // named parameter version
13 template <typename Graph, typename P, typename T, typename R>
15 dijkstra_shortest_paths(Graph& g,
16 typename graph_traits<Graph>::vertex_descriptor s,
17 const bgl_named_params<P, T, R>& params);
19 // non-named parameter version
20 template <typename Graph, typename DijkstraVisitor,
21 typename PredecessorMap, typename DistanceMap,
22 typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename CombineFunction,
23 typename DistInf, typename DistZero>
24 void dijkstra_shortest_paths
26 typename graph_traits<Graph>::vertex_descriptor s,
27 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
28 VertexIndexMap index_map,
29 CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
32 The ``dijkstra_shortest_paths()`` function solves the single-source
33 shortest paths problem on a weighted, undirected or directed
34 distributed graph. There are two implementations of distributed
35 Dijkstra's algorithm, which offer different performance
36 tradeoffs. Both are accessible via the ``dijkstra_shortest_paths()``
37 function (for compatibility with sequential BGL programs). The
38 distributed Dijkstra algorithms are very similar to their sequential
39 counterparts. Only the differences are highlighted here; please refer
40 to the `sequential Dijkstra implementation`_ for additional
41 details. The best-performing implementation for most cases is the
42 `Delta-Stepping algorithm`_; however, one can also employ the more
43 conservative `Crauser et al.'s algorithm`_ or the simlistic `Eager
44 Dijkstra's algorithm`_.
50 <``boost/graph/dijkstra_shortest_paths.hpp``>
55 All parameters of the `sequential Dijkstra implementation`_ are
56 supported and have essentially the same meaning. The distributed
57 Dijkstra implementations introduce a new parameter that allows one to
58 select `Eager Dijkstra's algorithm`_ and control the amount of work it
59 performs. Only differences and new parameters are documented here.
62 The graph type must be a model of `Distributed Graph`_.
65 IN: ``vertex_descriptor s``
66 The start vertex must be the same in every process.
69 OUT: ``predecessor_map(PredecessorMap p_map)``
70 The predecessor map must be a `Distributed Property Map`_ or
71 ``dummy_property_map``, although only the local portions of the map
74 **Default:** ``dummy_property_map``
77 UTIL/OUT: ``distance_map(DistanceMap d_map)``
78 The distance map must be either a `Distributed Property Map`_ or
79 ``dummy_property_map``. It will be given the ``vertex_distance``
83 IN: ``visitor(DijkstraVisitor vis)``
84 The visitor must be a distributed Dijkstra visitor. The suble differences
85 between sequential and distributed Dijkstra visitors are discussed in the
86 section `Visitor Event Points`_.
89 UTIL/OUT: ``color_map(ColorMap color)``
90 The color map must be a `Distributed Property Map`_ with the same
91 process group as the graph ``g`` whose colors must monotonically
92 darken (white -> gray -> black). The default value is a distributed
93 ``iterator_property_map`` created from a ``std::vector`` of
94 ``default_color_type``.
97 IN: ``lookahead(distance_type look)``
99 When this parameter is supplied, the implementation will use the
100 `Eager Dijkstra's algorithm`_ with the given lookahead value.
101 Lookahead permits distributed Dijkstra's algorithm to speculatively
102 process vertices whose shortest distance from the source may not
103 have been found yet. When the distance found is the shortest
104 distance, parallelism is improved and the algorithm may terminate
105 more quickly. However, if the distance is not the shortest distance,
106 the vertex will need to be reprocessed later, resulting in more
109 The type ``distance_type`` is the value type of the ``DistanceMap``
110 property map. It is a nonnegative value specifying how far ahead
111 Dijkstra's algorithm may process values.
113 **Default:** no value (lookahead is not employed; uses `Crauser et
118 The `Dijkstra Visitor`_ concept defines 7 event points that will be
119 triggered by the `sequential Dijkstra implementation`_. The distributed
120 Dijkstra retains these event points, but the sequence of events
121 triggered and the process in which each event occurs will change
122 depending on the distribution of the graph, lookahead, and edge
125 ``initialize_vertex(s, g)``
126 This will be invoked by every process for each local vertex.
129 ``discover_vertex(u, g)``
130 This will be invoked each type a process discovers a new vertex
131 ``u``. Due to incomplete information in distributed property maps,
132 this event may be triggered many times for the same vertex ``u``.
135 ``examine_vertex(u, g)``
136 This will be invoked by the process owning the vertex ``u``. This
137 event may be invoked multiple times for the same vertex when the
138 graph contains negative edges or lookahead is employed.
141 ``examine_edge(e, g)``
142 This will be invoked by the process owning the source vertex of
143 ``e``. As with ``examine_vertex``, this event may be invoked
144 multiple times for the same edge.
147 ``edge_relaxed(e, g)``
148 Similar to ``examine_edge``, this will be invoked by the process
149 owning the source vertex and may be invoked multiple times (even
150 without lookahead or negative edges).
153 ``edge_not_relaxed(e, g)``
154 Similar to ``edge_relaxed``. Some ``edge_not_relaxed`` events that
155 would be triggered by sequential Dijkstra's will become
156 ``edge_relaxed`` events in distributed Dijkstra's algorithm.
159 ``finish_vertex(e, g)``
160 See documentation for ``examine_vertex``. Note that a "finished"
161 vertex is not necessarily finished if lookahead is permitted or
162 negative edges exist in the graph.
165 Crauser et al.'s algorithm
166 --------------------------
171 template<typename DistributedGraph, typename DijkstraVisitor,
172 typename PredecessorMap, typename DistanceMap, typename WeightMap,
173 typename IndexMap, typename ColorMap, typename Compare,
174 typename Combine, typename DistInf, typename DistZero>
176 crauser_et_al_shortest_paths
177 (const DistributedGraph& g,
178 typename graph_traits<DistributedGraph>::vertex_descriptor s,
179 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
180 IndexMap index_map, ColorMap color_map,
181 Compare compare, Combine combine, DistInf inf, DistZero zero,
182 DijkstraVisitor vis);
184 template<typename DistributedGraph, typename DijkstraVisitor,
185 typename PredecessorMap, typename DistanceMap, typename WeightMap>
187 crauser_et_al_shortest_paths
188 (const DistributedGraph& g,
189 typename graph_traits<DistributedGraph>::vertex_descriptor s,
190 PredecessorMap predecessor, DistanceMap distance, WeightMap weight);
192 template<typename DistributedGraph, typename DijkstraVisitor,
193 typename PredecessorMap, typename DistanceMap>
195 crauser_et_al_shortest_paths
196 (const DistributedGraph& g,
197 typename graph_traits<DistributedGraph>::vertex_descriptor s,
198 PredecessorMap predecessor, DistanceMap distance);
201 The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer,
202 and Sanders [CMMS98a]_ improves the scalability of parallel Dijkstra's
203 algorithm by increasing the number of vertices that can be processed
204 in a given superstep. This algorithm adapts well to various graph
205 types, and is a simple algorithm to use, requiring no additional user
206 input to achieve reasonable performance. The disadvantage of this
207 algorithm is that the implementation is required to manage three
208 priority queues, which creates a large amount of work at each node.
210 This algorithm is used by default in distributed
211 ``dijkstra_shortest_paths()``.
215 <``boost/graph/distributed/crauser_et_al_shortest_paths.hpp``>
219 This algorithm performs *O(V log V)* work in *d + 1* BSP supersteps,
220 where *d* is at most *O(V)* but is generally much smaller. On directed
221 Erdos-Renyi graphs with edge weights in [0, 1), the expected number of
222 supersteps *d* is *O(n^(1/3))* with high probability.
226 The following charts illustrate the performance of the Parallel BGL implementation of Crauser et al.'s
227 algorithm on graphs with edge weights uniformly selected from the
230 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4
232 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1
234 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4
236 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1
239 Eager Dijkstra's algorithm
240 --------------------------
245 template<typename DistributedGraph, typename DijkstraVisitor,
246 typename PredecessorMap, typename DistanceMap, typename WeightMap,
247 typename IndexMap, typename ColorMap, typename Compare,
248 typename Combine, typename DistInf, typename DistZero>
250 eager_dijkstra_shortest_paths
251 (const DistributedGraph& g,
252 typename graph_traits<DistributedGraph>::vertex_descriptor s,
253 PredecessorMap predecessor, DistanceMap distance,
254 typename property_traits<DistanceMap>::value_type lookahead,
255 WeightMap weight, IndexMap index_map, ColorMap color_map,
256 Compare compare, Combine combine, DistInf inf, DistZero zero,
257 DijkstraVisitor vis);
259 template<typename DistributedGraph, typename DijkstraVisitor,
260 typename PredecessorMap, typename DistanceMap, typename WeightMap>
262 eager_dijkstra_shortest_paths
263 (const DistributedGraph& g,
264 typename graph_traits<DistributedGraph>::vertex_descriptor s,
265 PredecessorMap predecessor, DistanceMap distance,
266 typename property_traits<DistanceMap>::value_type lookahead,
269 template<typename DistributedGraph, typename DijkstraVisitor,
270 typename PredecessorMap, typename DistanceMap>
272 eager_dijkstra_shortest_paths
273 (const DistributedGraph& g,
274 typename graph_traits<DistributedGraph>::vertex_descriptor s,
275 PredecessorMap predecessor, DistanceMap distance,
276 typename property_traits<DistanceMap>::value_type lookahead);
279 In each superstep, parallel Dijkstra's algorithm typically only
280 processes nodes whose distances equivalent to the global minimum
281 distance, because these distances are guaranteed to be correct. This
282 variation on the algorithm allows the algorithm to process all
283 vertices whose distances are within some constant value of the
284 minimum distance. The value is called the "lookahead" value and is
285 provided by the user as the fifth parameter to the function. Small
286 values of the lookahead parameter will likely result in limited
287 parallelization opportunities, whereas large values will expose more
288 parallelism but may introduce (non-infinite) looping and result in
289 extra work. The optimal value for the lookahead parameter depends on
290 the input graph; see [CMMS98b]_ and [MS98]_.
292 This algorithm will be used by ``dijkstra_shortest_paths()`` when it
293 is provided with a lookahead value.
297 <``boost/graph/distributed/eager_dijkstra_shortest_paths.hpp``>
301 This algorithm performs *O(V log V)* work in *d
302 + 1* BSP supersteps, where *d* is at most *O(V)* but may be smaller
303 depending on the lookahead value. the algorithm may perform more work
304 when a large lookahead is provided, because vertices will be
309 The performance of the eager Dijkstra's algorithm varies greatly
310 depending on the lookahead value. The following charts illustrate the
311 performance of the Parallel BGL on graphs with edge weights uniformly
312 selected from the range *[0, 1)* and a constant lookahead of 0.1.
314 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5
316 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5&speedup=1
318 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5
320 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5&speedup=1
322 Delta-Stepping algorithm
323 --------------------------
327 namespace boost { namespace graph { namespace distributed {
329 template <typename Graph, typename PredecessorMap,
330 typename DistanceMap, typename WeightMap>
331 void delta_stepping_shortest_paths
333 typename graph_traits<Graph>::vertex_descriptor s,
334 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
335 typename property_traits<WeightMap>::value_type delta)
338 template <typename Graph, typename PredecessorMap,
339 typename DistanceMap, typename WeightMap>
340 void delta_stepping_shortest_paths
342 typename graph_traits<Graph>::vertex_descriptor s,
343 PredecessorMap predecessor, DistanceMap distance, WeightMap weight)
349 The delta-stepping algorithm [MS98]_ is another variant of the parallel
350 Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a
351 lookahead (``delta``) value that allows processors to process vertices
352 before we are guaranteed to find their minimum distances, permitting
353 more parallelism than a conservative strategy. Delta-stepping also
354 introduces a multi-level bucket data structure that provides more
355 relaxed ordering constraints than the priority queues employed by the
356 other Dijkstra variants, reducing the complexity of insertions,
357 relaxations, and removals from the central data structure. The
358 delta-stepping algorithm is the best-performing of the Dijkstra
361 The lookahead value ``delta`` determines how large each of the
362 "buckets" within the delta-stepping queue will be, where the ith
363 bucket contains edges within tentative distances between ``delta``*i
364 and ``delta``*(i+1). ``delta`` must be a positive value. When omitted,
365 ``delta`` will be set to the maximum edge weight divided by the
370 <``boost/graph/distributed/delta_stepping_shortest_paths.hpp``>
374 See the separate `Dijkstra example`_.
380 .. [CMMS98a] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A
381 Parallelization of Dijkstra's Shortest Path Algorithm. In
382 *Mathematical Foundations of Computer Science (MFCS)*, volume 1450 of
383 Lecture Notes in Computer Science, pages 722--731, 1998. Springer.
385 .. [CMMS98b] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
386 Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical
387 report, MPI-Informatik, 1998.
389 .. [MS98] Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel
390 shortest path algorithm. In *6th ESA*, LNCS. Springer, 1998.
392 -----------------------------------------------------------------------------
394 Copyright (C) 2004, 2005, 2006, 2007, 2008 The Trustees of Indiana University.
396 Authors: Douglas Gregor and Andrew Lumsdaine
398 .. |Logo| image:: pbgl-logo.png
401 :target: http://www.osl.iu.edu/research/pbgl
403 .. _sequential Dijkstra implementation: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
404 .. _distributed breadth-first search: breadth_first_search.html
405 .. _Distributed Graph: DistributedGraph.html
406 .. _Distributed Property Map: distributed_property_map.html
407 .. _Dijkstra Visitor: http://www.boost.org/libs/graph/doc/DijkstraVisitor.html
408 .. _Dijkstra example: dijkstra_example.html