ceph/src/boost/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html

   1 <?xml version="1.0" encoding="utf-8" ?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   6 <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
   7 <title>Parallel BGL Dijkstra's Single-Source Shortest Paths</title>
   8 <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
   9 </head>
  10 <body>
  11 <div class="document" id="logo-dijkstra-s-single-source-shortest-paths">
  12 <h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Dijkstra's Single-Source Shortest Paths</h1>
  13
  14 <!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
  15 Use, modification and distribution is subject to the Boost Software
  16 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  17 http://www.boost.org/LICENSE_1_0.txt) -->
  18 <pre class="literal-block">
  19 // named parameter version
  20 template &lt;typename Graph, typename P, typename T, typename R&gt;
  21 void
  22 dijkstra_shortest_paths(Graph&amp; g,
  23   typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
  24   const bgl_named_params&lt;P, T, R&gt;&amp; params);
  25
  26 // non-named parameter version
  27 template &lt;typename Graph, typename DijkstraVisitor,
  28           typename PredecessorMap, typename DistanceMap,
  29           typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename CombineFunction,
  30           typename DistInf, typename DistZero&gt;
  31 void dijkstra_shortest_paths
  32   (const Graph&amp; g,
  33    typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
  34    PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
  35    VertexIndexMap index_map,
  36    CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
  37    DijkstraVisitor vis);
  38 </pre>
  39 <p>The <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths()</span></tt> function solves the single-source
  40 shortest paths problem on a weighted, undirected or directed
  41 distributed graph. There are two implementations of distributed
  42 Dijkstra's algorithm, which offer different performance
  43 tradeoffs. Both are accessible via the <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths()</span></tt>
  44 function (for compatibility with sequential BGL programs). The
  45 distributed Dijkstra algorithms are very similar to their sequential
  46 counterparts. Only the differences are highlighted here; please refer
  47 to the <a class="reference external" href="http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html">sequential Dijkstra implementation</a> for additional
  48 details. The best-performing implementation for most cases is the
  49 <a class="reference internal" href="#delta-stepping-algorithm">Delta-Stepping algorithm</a>; however, one can also employ the more
  50 conservative <a class="reference internal" href="#crauser-et-al-s-algorithm">Crauser et al.'s algorithm</a> or the simlistic  <a class="reference internal" href="#eager-dijkstra-s-algorithm">Eager
  51 Dijkstra's algorithm</a>.</p>
  52 <div class="contents topic" id="contents">
  53 <p class="topic-title first">Contents</p>
  54 <ul class="simple">
  55 <li><a class="reference internal" href="#where-defined" id="id10">Where Defined</a></li>
  56 <li><a class="reference internal" href="#parameters" id="id11">Parameters</a></li>
  57 <li><a class="reference internal" href="#visitor-event-points" id="id12">Visitor Event Points</a></li>
  58 <li><a class="reference internal" href="#crauser-et-al-s-algorithm" id="id13">Crauser et al.'s algorithm</a><ul>
  59 <li><a class="reference internal" href="#id2" id="id14">Where Defined</a></li>
  60 <li><a class="reference internal" href="#complexity" id="id15">Complexity</a></li>
  61 <li><a class="reference internal" href="#performance" id="id16">Performance</a></li>
  62 </ul>
  63 </li>
  64 <li><a class="reference internal" href="#eager-dijkstra-s-algorithm" id="id17">Eager Dijkstra's algorithm</a><ul>
  65 <li><a class="reference internal" href="#id5" id="id18">Where Defined</a></li>
  66 <li><a class="reference internal" href="#id6" id="id19">Complexity</a></li>
  67 <li><a class="reference internal" href="#id7" id="id20">Performance</a></li>
  68 </ul>
  69 </li>
  70 <li><a class="reference internal" href="#delta-stepping-algorithm" id="id21">Delta-Stepping algorithm</a><ul>
  71 <li><a class="reference internal" href="#id9" id="id22">Where Defined</a></li>
  72 </ul>
  73 </li>
  74 <li><a class="reference internal" href="#example" id="id23">Example</a></li>
  75 <li><a class="reference internal" href="#bibliography" id="id24">Bibliography</a></li>
  76 </ul>
  77 </div>
  78 <div class="section" id="where-defined">
  79 <h1><a class="toc-backref" href="#id10">Where Defined</a></h1>
  80 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/dijkstra_shortest_paths.hpp</span></tt>&gt;</p>
  81 </div>
  82 <div class="section" id="parameters">
  83 <h1><a class="toc-backref" href="#id11">Parameters</a></h1>
  84 <p>All parameters of the <a class="reference external" href="http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html">sequential Dijkstra implementation</a> are
  85 supported and have essentially the same meaning. The distributed
  86 Dijkstra implementations introduce a new parameter that allows one to
  87 select <a class="reference internal" href="#eager-dijkstra-s-algorithm">Eager Dijkstra's algorithm</a> and control the amount of work it
  88 performs. Only differences and new parameters are documented here.</p>
  89 <dl class="docutils">
  90 <dt>IN: <tt class="docutils literal"><span class="pre">Graph&amp;</span> <span class="pre">g</span></tt></dt>
  91 <dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.</dd>
  92 <dt>IN: <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">s</span></tt></dt>
  93 <dd>The start vertex must be the same in every process.</dd>
  94 <dt>OUT: <tt class="docutils literal"><span class="pre">predecessor_map(PredecessorMap</span> <span class="pre">p_map)</span></tt></dt>
  95 <dd><p class="first">The predecessor map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> or
  96 <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>, although only the local portions of the map
  97 will be written.</p>
  98 <p class="last"><strong>Default:</strong> <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt></p>
  99 </dd>
 100 <dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">distance_map(DistanceMap</span> <span class="pre">d_map)</span></tt></dt>
 101 <dd>The distance map must be either a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> or
 102 <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>. It will be given the <tt class="docutils literal"><span class="pre">vertex_distance</span></tt>
 103 role.</dd>
 104 <dt>IN: <tt class="docutils literal"><span class="pre">visitor(DijkstraVisitor</span> <span class="pre">vis)</span></tt></dt>
 105 <dd>The visitor must be a distributed Dijkstra visitor. The suble differences
 106 between sequential and distributed Dijkstra visitors are discussed in the
 107 section <a class="reference internal" href="#visitor-event-points">Visitor Event Points</a>.</dd>
 108 <dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">color_map(ColorMap</span> <span class="pre">color)</span></tt></dt>
 109 <dd>The color map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same
 110 process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose colors must monotonically
 111 darken (white -&gt; gray -&gt; black). The default value is a distributed
 112 <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a <tt class="docutils literal"><span class="pre">std::vector</span></tt> of
 113 <tt class="docutils literal"><span class="pre">default_color_type</span></tt>.</dd>
 114 </dl>
 115 <p>IN: <tt class="docutils literal"><span class="pre">lookahead(distance_type</span> <span class="pre">look)</span></tt></p>
 116 <blockquote>
 117 <p>When this parameter is supplied, the implementation will use the
 118 <a class="reference internal" href="#eager-dijkstra-s-algorithm">Eager Dijkstra's algorithm</a> with the given lookahead value.
 119 Lookahead permits distributed Dijkstra's algorithm to speculatively
 120 process vertices whose shortest distance from the source may not
 121 have been found yet. When the distance found is the shortest
 122 distance, parallelism is improved and the algorithm may terminate
 123 more quickly. However, if the distance is not the shortest distance,
 124 the vertex will need to be reprocessed later, resulting in more
 125 work.</p>
 126 <p>The type <tt class="docutils literal"><span class="pre">distance_type</span></tt> is the value type of the <tt class="docutils literal"><span class="pre">DistanceMap</span></tt>
 127 property map. It is a nonnegative value specifying how far ahead
 128 Dijkstra's algorithm may process values.</p>
 129 <p><strong>Default:</strong> no value (lookahead is not employed; uses <a class="reference internal" href="#crauser-et-al-s-algorithm">Crauser et
 130 al.'s algorithm</a>).</p>
 131 </blockquote>
 132 </div>
 133 <div class="section" id="visitor-event-points">
 134 <h1><a class="toc-backref" href="#id12">Visitor Event Points</a></h1>
 135 <p>The <a class="reference external" href="http://www.boost.org/libs/graph/doc/DijkstraVisitor.html">Dijkstra Visitor</a> concept defines 7 event points that will be
 136 triggered by the <a class="reference external" href="http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html">sequential Dijkstra implementation</a>. The distributed
 137 Dijkstra retains these event points, but the sequence of events
 138 triggered and the process in which each event occurs will change
 139 depending on the distribution of the graph, lookahead, and edge
 140 weights.</p>
 141 <dl class="docutils">
 142 <dt><tt class="docutils literal"><span class="pre">initialize_vertex(s,</span> <span class="pre">g)</span></tt></dt>
 143 <dd>This will be invoked by every process for each local vertex.</dd>
 144 <dt><tt class="docutils literal"><span class="pre">discover_vertex(u,</span> <span class="pre">g)</span></tt></dt>
 145 <dd>This will be invoked each type a process discovers a new vertex
 146 <tt class="docutils literal"><span class="pre">u</span></tt>. Due to incomplete information in distributed property maps,
 147 this event may be triggered many times for the same vertex <tt class="docutils literal"><span class="pre">u</span></tt>.</dd>
 148 <dt><tt class="docutils literal"><span class="pre">examine_vertex(u,</span> <span class="pre">g)</span></tt></dt>
 149 <dd>This will be invoked by the process owning the vertex <tt class="docutils literal"><span class="pre">u</span></tt>. This
 150 event may be invoked multiple times for the same vertex when the
 151 graph contains negative edges or lookahead is employed.</dd>
 152 <dt><tt class="docutils literal"><span class="pre">examine_edge(e,</span> <span class="pre">g)</span></tt></dt>
 153 <dd>This will be invoked by the process owning the source vertex of
 154 <tt class="docutils literal"><span class="pre">e</span></tt>. As with <tt class="docutils literal"><span class="pre">examine_vertex</span></tt>, this event may be invoked
 155 multiple times for the same edge.</dd>
 156 <dt><tt class="docutils literal"><span class="pre">edge_relaxed(e,</span> <span class="pre">g)</span></tt></dt>
 157 <dd>Similar to <tt class="docutils literal"><span class="pre">examine_edge</span></tt>, this will be invoked by the process
 158 owning the source vertex and may be invoked multiple times (even
 159 without lookahead or negative edges).</dd>
 160 <dt><tt class="docutils literal"><span class="pre">edge_not_relaxed(e,</span> <span class="pre">g)</span></tt></dt>
 161 <dd>Similar to <tt class="docutils literal"><span class="pre">edge_relaxed</span></tt>. Some <tt class="docutils literal"><span class="pre">edge_not_relaxed</span></tt> events that
 162 would be triggered by sequential Dijkstra's will become
 163 <tt class="docutils literal"><span class="pre">edge_relaxed</span></tt> events in distributed Dijkstra's algorithm.</dd>
 164 <dt><tt class="docutils literal"><span class="pre">finish_vertex(e,</span> <span class="pre">g)</span></tt></dt>
 165 <dd>See documentation for <tt class="docutils literal"><span class="pre">examine_vertex</span></tt>. Note that a &quot;finished&quot;
 166 vertex is not necessarily finished if lookahead is permitted or
 167 negative edges exist in the graph.</dd>
 168 </dl>
 169 </div>
 170 <div class="section" id="crauser-et-al-s-algorithm">
 171 <h1><a class="toc-backref" href="#id13">Crauser et al.'s algorithm</a></h1>
 172 <pre class="literal-block">
 173 namespace graph {
 174   template&lt;typename DistributedGraph, typename DijkstraVisitor,
 175            typename PredecessorMap, typename DistanceMap, typename WeightMap,
 176            typename IndexMap, typename ColorMap, typename Compare,
 177            typename Combine, typename DistInf, typename DistZero&gt;
 178   void
 179   crauser_et_al_shortest_paths
 180     (const DistributedGraph&amp; g,
 181      typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
 182      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 183      IndexMap index_map, ColorMap color_map,
 184      Compare compare, Combine combine, DistInf inf, DistZero zero,
 185      DijkstraVisitor vis);
 186
 187   template&lt;typename DistributedGraph, typename DijkstraVisitor,
 188            typename PredecessorMap, typename DistanceMap, typename WeightMap&gt;
 189   void
 190   crauser_et_al_shortest_paths
 191     (const DistributedGraph&amp; g,
 192      typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
 193      PredecessorMap predecessor, DistanceMap distance, WeightMap weight);
 194
 195   template&lt;typename DistributedGraph, typename DijkstraVisitor,
 196            typename PredecessorMap, typename DistanceMap&gt;
 197   void
 198   crauser_et_al_shortest_paths
 199     (const DistributedGraph&amp; g,
 200      typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
 201      PredecessorMap predecessor, DistanceMap distance);
 202 }
 203 </pre>
 204 <p>The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer,
 205 and Sanders <a class="citation-reference" href="#cmms98a" id="id1">[CMMS98a]</a> improves the scalability of parallel Dijkstra's
 206 algorithm by increasing the number of vertices that can be processed
 207 in a given superstep. This algorithm adapts well to various graph
 208 types, and is a simple algorithm to use, requiring no additional user
 209 input to achieve reasonable performance. The disadvantage of this
 210 algorithm is that the implementation is required to manage three
 211 priority queues, which creates a large amount of work at each node.</p>
 212 <p>This algorithm is used by default in distributed
 213 <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths()</span></tt>.</p>
 214 <div class="section" id="id2">
 215 <h2><a class="toc-backref" href="#id14">Where Defined</a></h2>
 216 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/crauser_et_al_shortest_paths.hpp</span></tt>&gt;</p>
 217 </div>
 218 <div class="section" id="complexity">
 219 <h2><a class="toc-backref" href="#id15">Complexity</a></h2>
 220 <p>This algorithm performs <em>O(V log V)</em> work in <em>d + 1</em> BSP supersteps,
 221 where <em>d</em> is at most <em>O(V)</em> but is generally much smaller. On directed
 222 Erdos-Renyi graphs with edge weights in [0, 1), the expected number of
 223 supersteps <em>d</em> is <em>O(n^(1/3))</em> with high probability.</p>
 224 </div>
 225 <div class="section" id="performance">
 226 <h2><a class="toc-backref" href="#id16">Performance</a></h2>
 227 <p>The following charts illustrate the performance of the Parallel BGL implementation of Crauser et al.'s
 228 algorithm on graphs with edge weights uniformly selected from the
 229 range <em>[0, 1)</em>.</p>
 230 <img align="left" alt="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png" class="align-left" src="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png" />
 231 <img alt="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png" src="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png" />
 232 <img align="left" alt="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_4.png" class="align-left" src="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_4.png" />
 233 <img alt="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png" src="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png" />
 234 </div>
 235 </div>
 236 <div class="section" id="eager-dijkstra-s-algorithm">
 237 <h1><a class="toc-backref" href="#id17">Eager Dijkstra's algorithm</a></h1>
 238 <pre class="literal-block">
 239 namespace graph {
 240   template&lt;typename DistributedGraph, typename DijkstraVisitor,
 241            typename PredecessorMap, typename DistanceMap, typename WeightMap,
 242            typename IndexMap, typename ColorMap, typename Compare,
 243            typename Combine, typename DistInf, typename DistZero&gt;
 244   void
 245   eager_dijkstra_shortest_paths
 246     (const DistributedGraph&amp; g,
 247      typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
 248      PredecessorMap predecessor, DistanceMap distance,
 249      typename property_traits&lt;DistanceMap&gt;::value_type lookahead,
 250      WeightMap weight, IndexMap index_map, ColorMap color_map,
 251      Compare compare, Combine combine, DistInf inf, DistZero zero,
 252      DijkstraVisitor vis);
 253
 254   template&lt;typename DistributedGraph, typename DijkstraVisitor,
 255            typename PredecessorMap, typename DistanceMap, typename WeightMap&gt;
 256   void
 257   eager_dijkstra_shortest_paths
 258     (const DistributedGraph&amp; g,
 259      typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
 260      PredecessorMap predecessor, DistanceMap distance,
 261      typename property_traits&lt;DistanceMap&gt;::value_type lookahead,
 262      WeightMap weight);
 263
 264   template&lt;typename DistributedGraph, typename DijkstraVisitor,
 265            typename PredecessorMap, typename DistanceMap&gt;
 266   void
 267   eager_dijkstra_shortest_paths
 268     (const DistributedGraph&amp; g,
 269      typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
 270      PredecessorMap predecessor, DistanceMap distance,
 271      typename property_traits&lt;DistanceMap&gt;::value_type lookahead);
 272 }
 273 </pre>
 274 <p>In each superstep, parallel Dijkstra's algorithm typically only
 275 processes nodes whose distances equivalent to the global minimum
 276 distance, because these distances are guaranteed to be correct. This
 277 variation on the algorithm allows the algorithm to process all
 278 vertices whose distances are within some constant value of the
 279 minimum distance. The value is called the &quot;lookahead&quot; value and is
 280 provided by the user as the fifth parameter to the function. Small
 281 values of the lookahead parameter will likely result in limited
 282 parallelization opportunities, whereas large values will expose more
 283 parallelism but may introduce (non-infinite) looping and result in
 284 extra work. The optimal value for the lookahead parameter depends on
 285 the input graph; see <a class="citation-reference" href="#cmms98b" id="id3">[CMMS98b]</a> and <a class="citation-reference" href="#ms98" id="id4">[MS98]</a>.</p>
 286 <p>This algorithm will be used by <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths()</span></tt> when it
 287 is provided with a lookahead value.</p>
 288 <div class="section" id="id5">
 289 <h2><a class="toc-backref" href="#id18">Where Defined</a></h2>
 290 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/eager_dijkstra_shortest_paths.hpp</span></tt>&gt;</p>
 291 </div>
 292 <div class="section" id="id6">
 293 <h2><a class="toc-backref" href="#id19">Complexity</a></h2>
 294 <p>This algorithm performs <em>O(V log V)</em> work in <em>d
 295 + 1</em> BSP supersteps, where <em>d</em> is at most <em>O(V)</em> but may be smaller
 296 depending on the lookahead value. the algorithm may perform more work
 297 when a large lookahead is provided, because vertices will be
 298 reprocessed.</p>
 299 </div>
 300 <div class="section" id="id7">
 301 <h2><a class="toc-backref" href="#id20">Performance</a></h2>
 302 <p>The performance of the eager Dijkstra's algorithm varies greatly
 303 depending on the lookahead value. The following charts illustrate the
 304 performance of the Parallel BGL on graphs with edge weights uniformly
 305 selected from the range <em>[0, 1)</em> and a constant lookahead of 0.1.</p>
 306 <img align="left" alt="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png" class="align-left" src="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png" />
 307 <img alt="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png" src="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png" />
 308 <img align="left" alt="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_5.png" class="align-left" src="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_5.png" />
 309 <img alt="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png" src="chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png" />
 310 </div>
 311 </div>
 312 <div class="section" id="delta-stepping-algorithm">
 313 <h1><a class="toc-backref" href="#id21">Delta-Stepping algorithm</a></h1>
 314 <pre class="literal-block">
 315 namespace boost { namespace graph { namespace distributed {
 316
 317   template &lt;typename Graph, typename PredecessorMap,
 318             typename DistanceMap, typename WeightMap&gt;
 319   void delta_stepping_shortest_paths
 320     (const Graph&amp; g,
 321      typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
 322      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 323      typename property_traits&lt;WeightMap&gt;::value_type delta)
 324
 325
 326   template &lt;typename Graph, typename PredecessorMap,
 327             typename DistanceMap, typename WeightMap&gt;
 328   void delta_stepping_shortest_paths
 329     (const Graph&amp; g,
 330      typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
 331      PredecessorMap predecessor, DistanceMap distance, WeightMap weight)
 332   }
 333
 334 } } }
 335 </pre>
 336 <p>The delta-stepping algorithm <a class="citation-reference" href="#ms98" id="id8">[MS98]</a> is another variant of the parallel
 337 Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a
 338 lookahead (<tt class="docutils literal"><span class="pre">delta</span></tt>) value that allows processors to process vertices
 339 before we are guaranteed to find their minimum distances, permitting
 340 more parallelism than a conservative strategy. Delta-stepping also
 341 introduces a multi-level bucket data structure that provides more
 342 relaxed ordering constraints than the priority queues employed by the
 343 other Dijkstra variants, reducing the complexity of insertions,
 344 relaxations, and removals from the central data structure. The
 345 delta-stepping algorithm is the best-performing of the Dijkstra
 346 variants.</p>
 347 <p>The lookahead value <tt class="docutils literal"><span class="pre">delta</span></tt> determines how large each of the
 348 &quot;buckets&quot; within the delta-stepping queue will be, where the ith
 349 bucket contains edges within tentative distances between <tt class="docutils literal"><span class="pre">delta``*i</span>
 350 <span class="pre">and</span> <span class="pre">``delta``*(i+1).</span> <span class="pre">``delta</span></tt> must be a positive value. When omitted,
 351 <tt class="docutils literal"><span class="pre">delta</span></tt> will be set to the maximum edge weight divided by the
 352 maximum degree.</p>
 353 <div class="section" id="id9">
 354 <h2><a class="toc-backref" href="#id22">Where Defined</a></h2>
 355 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/delta_stepping_shortest_paths.hpp</span></tt>&gt;</p>
 356 </div>
 357 </div>
 358 <div class="section" id="example">
 359 <h1><a class="toc-backref" href="#id23">Example</a></h1>
 360 <p>See the separate <a class="reference external" href="dijkstra_example.html">Dijkstra example</a>.</p>
 361 </div>
 362 <div class="section" id="bibliography">
 363 <h1><a class="toc-backref" href="#id24">Bibliography</a></h1>
 364 <table class="docutils citation" frame="void" id="cmms98a" rules="none">
 365 <colgroup><col class="label" /><col /></colgroup>
 366 <tbody valign="top">
 367 <tr><td class="label"><a class="fn-backref" href="#id1">[CMMS98a]</a></td><td>Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A
 368 Parallelization of Dijkstra's Shortest Path Algorithm. In
 369 <em>Mathematical Foundations of Computer Science (MFCS)</em>, volume 1450 of
 370 Lecture Notes in Computer Science, pages 722--731, 1998. Springer.</td></tr>
 371 </tbody>
 372 </table>
 373 <table class="docutils citation" frame="void" id="cmms98b" rules="none">
 374 <colgroup><col class="label" /><col /></colgroup>
 375 <tbody valign="top">
 376 <tr><td class="label"><a class="fn-backref" href="#id3">[CMMS98b]</a></td><td>Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
 377 Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical
 378 report, MPI-Informatik, 1998.</td></tr>
 379 </tbody>
 380 </table>
 381 <table class="docutils citation" frame="void" id="ms98" rules="none">
 382 <colgroup><col class="label" /><col /></colgroup>
 383 <tbody valign="top">
 384 <tr><td class="label">[MS98]</td><td><em>(<a class="fn-backref" href="#id4">1</a>, <a class="fn-backref" href="#id8">2</a>)</em> Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel
 385 shortest path algorithm. In <em>6th ESA</em>, LNCS. Springer, 1998.</td></tr>
 386 </tbody>
 387 </table>
 388 <hr class="docutils" />
 389 <p>Copyright (C) 2004, 2005, 2006, 2007, 2008 The Trustees of Indiana University.</p>
 390 <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
 391 </div>
 392 </div>
 393 <div class="footer">
 394 <hr class="footer" />
 395 Generated on: 2009-05-31 00:21 UTC.
 396 Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
 397
 398 </div>
 399 </body>
 400 </html>