123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400 |
- <?xml version="1.0" encoding="utf-8" ?>
- <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
- <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
- <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
- <title>Parallel BGL Dijkstra's Single-Source Shortest Paths</title>
- <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-dijkstra-s-single-source-shortest-paths">
- <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>
- <!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
- Use, modification and distribution is subject to the Boost Software
- License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt) -->
- <pre class="literal-block">
- // named parameter version
- template <typename Graph, typename P, typename T, typename R>
- void
- dijkstra_shortest_paths(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- const bgl_named_params<P, T, R>& params);
- // non-named parameter version
- template <typename Graph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap,
- typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename CombineFunction,
- typename DistInf, typename DistZero>
- void dijkstra_shortest_paths
- (const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
- VertexIndexMap index_map,
- CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
- DijkstraVisitor vis);
- </pre>
- <p>The <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths()</span></tt> function solves the single-source
- shortest paths problem on a weighted, undirected or directed
- distributed graph. There are two implementations of distributed
- Dijkstra's algorithm, which offer different performance
- tradeoffs. Both are accessible via the <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths()</span></tt>
- function (for compatibility with sequential BGL programs). The
- distributed Dijkstra algorithms are very similar to their sequential
- counterparts. Only the differences are highlighted here; please refer
- to the <a class="reference external" href="http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html">sequential Dijkstra implementation</a> for additional
- details. The best-performing implementation for most cases is the
- <a class="reference internal" href="#delta-stepping-algorithm">Delta-Stepping algorithm</a>; however, one can also employ the more
- 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
- Dijkstra's algorithm</a>.</p>
- <div class="contents topic" id="contents">
- <p class="topic-title first">Contents</p>
- <ul class="simple">
- <li><a class="reference internal" href="#where-defined" id="id10">Where Defined</a></li>
- <li><a class="reference internal" href="#parameters" id="id11">Parameters</a></li>
- <li><a class="reference internal" href="#visitor-event-points" id="id12">Visitor Event Points</a></li>
- <li><a class="reference internal" href="#crauser-et-al-s-algorithm" id="id13">Crauser et al.'s algorithm</a><ul>
- <li><a class="reference internal" href="#id2" id="id14">Where Defined</a></li>
- <li><a class="reference internal" href="#complexity" id="id15">Complexity</a></li>
- <li><a class="reference internal" href="#performance" id="id16">Performance</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#eager-dijkstra-s-algorithm" id="id17">Eager Dijkstra's algorithm</a><ul>
- <li><a class="reference internal" href="#id5" id="id18">Where Defined</a></li>
- <li><a class="reference internal" href="#id6" id="id19">Complexity</a></li>
- <li><a class="reference internal" href="#id7" id="id20">Performance</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#delta-stepping-algorithm" id="id21">Delta-Stepping algorithm</a><ul>
- <li><a class="reference internal" href="#id9" id="id22">Where Defined</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#example" id="id23">Example</a></li>
- <li><a class="reference internal" href="#bibliography" id="id24">Bibliography</a></li>
- </ul>
- </div>
- <div class="section" id="where-defined">
- <h1><a class="toc-backref" href="#id10">Where Defined</a></h1>
- <p><<tt class="docutils literal"><span class="pre">boost/graph/dijkstra_shortest_paths.hpp</span></tt>></p>
- </div>
- <div class="section" id="parameters">
- <h1><a class="toc-backref" href="#id11">Parameters</a></h1>
- <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
- supported and have essentially the same meaning. The distributed
- Dijkstra implementations introduce a new parameter that allows one to
- select <a class="reference internal" href="#eager-dijkstra-s-algorithm">Eager Dijkstra's algorithm</a> and control the amount of work it
- performs. Only differences and new parameters are documented here.</p>
- <dl class="docutils">
- <dt>IN: <tt class="docutils literal"><span class="pre">Graph&</span> <span class="pre">g</span></tt></dt>
- <dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.</dd>
- <dt>IN: <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">s</span></tt></dt>
- <dd>The start vertex must be the same in every process.</dd>
- <dt>OUT: <tt class="docutils literal"><span class="pre">predecessor_map(PredecessorMap</span> <span class="pre">p_map)</span></tt></dt>
- <dd><p class="first">The predecessor map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> or
- <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>, although only the local portions of the map
- will be written.</p>
- <p class="last"><strong>Default:</strong> <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt></p>
- </dd>
- <dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">distance_map(DistanceMap</span> <span class="pre">d_map)</span></tt></dt>
- <dd>The distance map must be either a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> or
- <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>
- role.</dd>
- <dt>IN: <tt class="docutils literal"><span class="pre">visitor(DijkstraVisitor</span> <span class="pre">vis)</span></tt></dt>
- <dd>The visitor must be a distributed Dijkstra visitor. The suble differences
- between sequential and distributed Dijkstra visitors are discussed in the
- section <a class="reference internal" href="#visitor-event-points">Visitor Event Points</a>.</dd>
- <dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">color_map(ColorMap</span> <span class="pre">color)</span></tt></dt>
- <dd>The color map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same
- process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose colors must monotonically
- darken (white -> gray -> black). The default value is a distributed
- <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
- <tt class="docutils literal"><span class="pre">default_color_type</span></tt>.</dd>
- </dl>
- <p>IN: <tt class="docutils literal"><span class="pre">lookahead(distance_type</span> <span class="pre">look)</span></tt></p>
- <blockquote>
- <p>When this parameter is supplied, the implementation will use the
- <a class="reference internal" href="#eager-dijkstra-s-algorithm">Eager Dijkstra's algorithm</a> with the given lookahead value.
- Lookahead permits distributed Dijkstra's algorithm to speculatively
- process vertices whose shortest distance from the source may not
- have been found yet. When the distance found is the shortest
- distance, parallelism is improved and the algorithm may terminate
- more quickly. However, if the distance is not the shortest distance,
- the vertex will need to be reprocessed later, resulting in more
- work.</p>
- <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>
- property map. It is a nonnegative value specifying how far ahead
- Dijkstra's algorithm may process values.</p>
- <p><strong>Default:</strong> no value (lookahead is not employed; uses <a class="reference internal" href="#crauser-et-al-s-algorithm">Crauser et
- al.'s algorithm</a>).</p>
- </blockquote>
- </div>
- <div class="section" id="visitor-event-points">
- <h1><a class="toc-backref" href="#id12">Visitor Event Points</a></h1>
- <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
- 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
- Dijkstra retains these event points, but the sequence of events
- triggered and the process in which each event occurs will change
- depending on the distribution of the graph, lookahead, and edge
- weights.</p>
- <dl class="docutils">
- <dt><tt class="docutils literal"><span class="pre">initialize_vertex(s,</span> <span class="pre">g)</span></tt></dt>
- <dd>This will be invoked by every process for each local vertex.</dd>
- <dt><tt class="docutils literal"><span class="pre">discover_vertex(u,</span> <span class="pre">g)</span></tt></dt>
- <dd>This will be invoked each type a process discovers a new vertex
- <tt class="docutils literal"><span class="pre">u</span></tt>. Due to incomplete information in distributed property maps,
- this event may be triggered many times for the same vertex <tt class="docutils literal"><span class="pre">u</span></tt>.</dd>
- <dt><tt class="docutils literal"><span class="pre">examine_vertex(u,</span> <span class="pre">g)</span></tt></dt>
- <dd>This will be invoked by the process owning the vertex <tt class="docutils literal"><span class="pre">u</span></tt>. This
- event may be invoked multiple times for the same vertex when the
- graph contains negative edges or lookahead is employed.</dd>
- <dt><tt class="docutils literal"><span class="pre">examine_edge(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>This will be invoked by the process owning the source vertex of
- <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
- multiple times for the same edge.</dd>
- <dt><tt class="docutils literal"><span class="pre">edge_relaxed(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>Similar to <tt class="docutils literal"><span class="pre">examine_edge</span></tt>, this will be invoked by the process
- owning the source vertex and may be invoked multiple times (even
- without lookahead or negative edges).</dd>
- <dt><tt class="docutils literal"><span class="pre">edge_not_relaxed(e,</span> <span class="pre">g)</span></tt></dt>
- <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
- would be triggered by sequential Dijkstra's will become
- <tt class="docutils literal"><span class="pre">edge_relaxed</span></tt> events in distributed Dijkstra's algorithm.</dd>
- <dt><tt class="docutils literal"><span class="pre">finish_vertex(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>See documentation for <tt class="docutils literal"><span class="pre">examine_vertex</span></tt>. Note that a "finished"
- vertex is not necessarily finished if lookahead is permitted or
- negative edges exist in the graph.</dd>
- </dl>
- </div>
- <div class="section" id="crauser-et-al-s-algorithm">
- <h1><a class="toc-backref" href="#id13">Crauser et al.'s algorithm</a></h1>
- <pre class="literal-block">
- namespace graph {
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap, typename WeightMap,
- typename IndexMap, typename ColorMap, typename Compare,
- typename Combine, typename DistInf, typename DistZero>
- void
- crauser_et_al_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
- IndexMap index_map, ColorMap color_map,
- Compare compare, Combine combine, DistInf inf, DistZero zero,
- DijkstraVisitor vis);
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap, typename WeightMap>
- void
- crauser_et_al_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight);
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap>
- void
- crauser_et_al_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance);
- }
- </pre>
- <p>The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer,
- and Sanders <a class="citation-reference" href="#cmms98a" id="id1">[CMMS98a]</a> improves the scalability of parallel Dijkstra's
- algorithm by increasing the number of vertices that can be processed
- in a given superstep. This algorithm adapts well to various graph
- types, and is a simple algorithm to use, requiring no additional user
- input to achieve reasonable performance. The disadvantage of this
- algorithm is that the implementation is required to manage three
- priority queues, which creates a large amount of work at each node.</p>
- <p>This algorithm is used by default in distributed
- <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths()</span></tt>.</p>
- <div class="section" id="id2">
- <h2><a class="toc-backref" href="#id14">Where Defined</a></h2>
- <p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/crauser_et_al_shortest_paths.hpp</span></tt>></p>
- </div>
- <div class="section" id="complexity">
- <h2><a class="toc-backref" href="#id15">Complexity</a></h2>
- <p>This algorithm performs <em>O(V log V)</em> work in <em>d + 1</em> BSP supersteps,
- where <em>d</em> is at most <em>O(V)</em> but is generally much smaller. On directed
- Erdos-Renyi graphs with edge weights in [0, 1), the expected number of
- supersteps <em>d</em> is <em>O(n^(1/3))</em> with high probability.</p>
- </div>
- <div class="section" id="performance">
- <h2><a class="toc-backref" href="#id16">Performance</a></h2>
- <p>The following charts illustrate the performance of the Parallel BGL implementation of Crauser et al.'s
- algorithm on graphs with edge weights uniformly selected from the
- range <em>[0, 1)</em>.</p>
- <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" />
- <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" />
- <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" />
- <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" />
- </div>
- </div>
- <div class="section" id="eager-dijkstra-s-algorithm">
- <h1><a class="toc-backref" href="#id17">Eager Dijkstra's algorithm</a></h1>
- <pre class="literal-block">
- namespace graph {
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap, typename WeightMap,
- typename IndexMap, typename ColorMap, typename Compare,
- typename Combine, typename DistInf, typename DistZero>
- void
- eager_dijkstra_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance,
- typename property_traits<DistanceMap>::value_type lookahead,
- WeightMap weight, IndexMap index_map, ColorMap color_map,
- Compare compare, Combine combine, DistInf inf, DistZero zero,
- DijkstraVisitor vis);
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap, typename WeightMap>
- void
- eager_dijkstra_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance,
- typename property_traits<DistanceMap>::value_type lookahead,
- WeightMap weight);
- template<typename DistributedGraph, typename DijkstraVisitor,
- typename PredecessorMap, typename DistanceMap>
- void
- eager_dijkstra_shortest_paths
- (const DistributedGraph& g,
- typename graph_traits<DistributedGraph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance,
- typename property_traits<DistanceMap>::value_type lookahead);
- }
- </pre>
- <p>In each superstep, parallel Dijkstra's algorithm typically only
- processes nodes whose distances equivalent to the global minimum
- distance, because these distances are guaranteed to be correct. This
- variation on the algorithm allows the algorithm to process all
- vertices whose distances are within some constant value of the
- minimum distance. The value is called the "lookahead" value and is
- provided by the user as the fifth parameter to the function. Small
- values of the lookahead parameter will likely result in limited
- parallelization opportunities, whereas large values will expose more
- parallelism but may introduce (non-infinite) looping and result in
- extra work. The optimal value for the lookahead parameter depends on
- 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>
- <p>This algorithm will be used by <tt class="docutils literal"><span class="pre">dijkstra_shortest_paths()</span></tt> when it
- is provided with a lookahead value.</p>
- <div class="section" id="id5">
- <h2><a class="toc-backref" href="#id18">Where Defined</a></h2>
- <p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/eager_dijkstra_shortest_paths.hpp</span></tt>></p>
- </div>
- <div class="section" id="id6">
- <h2><a class="toc-backref" href="#id19">Complexity</a></h2>
- <p>This algorithm performs <em>O(V log V)</em> work in <em>d
- + 1</em> BSP supersteps, where <em>d</em> is at most <em>O(V)</em> but may be smaller
- depending on the lookahead value. the algorithm may perform more work
- when a large lookahead is provided, because vertices will be
- reprocessed.</p>
- </div>
- <div class="section" id="id7">
- <h2><a class="toc-backref" href="#id20">Performance</a></h2>
- <p>The performance of the eager Dijkstra's algorithm varies greatly
- depending on the lookahead value. The following charts illustrate the
- performance of the Parallel BGL on graphs with edge weights uniformly
- selected from the range <em>[0, 1)</em> and a constant lookahead of 0.1.</p>
- <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" />
- <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" />
- <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" />
- <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" />
- </div>
- </div>
- <div class="section" id="delta-stepping-algorithm">
- <h1><a class="toc-backref" href="#id21">Delta-Stepping algorithm</a></h1>
- <pre class="literal-block">
- namespace boost { namespace graph { namespace distributed {
- template <typename Graph, typename PredecessorMap,
- typename DistanceMap, typename WeightMap>
- void delta_stepping_shortest_paths
- (const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
- typename property_traits<WeightMap>::value_type delta)
- template <typename Graph, typename PredecessorMap,
- typename DistanceMap, typename WeightMap>
- void delta_stepping_shortest_paths
- (const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- PredecessorMap predecessor, DistanceMap distance, WeightMap weight)
- }
- } } }
- </pre>
- <p>The delta-stepping algorithm <a class="citation-reference" href="#ms98" id="id8">[MS98]</a> is another variant of the parallel
- Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a
- lookahead (<tt class="docutils literal"><span class="pre">delta</span></tt>) value that allows processors to process vertices
- before we are guaranteed to find their minimum distances, permitting
- more parallelism than a conservative strategy. Delta-stepping also
- introduces a multi-level bucket data structure that provides more
- relaxed ordering constraints than the priority queues employed by the
- other Dijkstra variants, reducing the complexity of insertions,
- relaxations, and removals from the central data structure. The
- delta-stepping algorithm is the best-performing of the Dijkstra
- variants.</p>
- <p>The lookahead value <tt class="docutils literal"><span class="pre">delta</span></tt> determines how large each of the
- "buckets" within the delta-stepping queue will be, where the ith
- bucket contains edges within tentative distances between <tt class="docutils literal"><span class="pre">delta``*i</span>
- <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,
- <tt class="docutils literal"><span class="pre">delta</span></tt> will be set to the maximum edge weight divided by the
- maximum degree.</p>
- <div class="section" id="id9">
- <h2><a class="toc-backref" href="#id22">Where Defined</a></h2>
- <p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/delta_stepping_shortest_paths.hpp</span></tt>></p>
- </div>
- </div>
- <div class="section" id="example">
- <h1><a class="toc-backref" href="#id23">Example</a></h1>
- <p>See the separate <a class="reference external" href="dijkstra_example.html">Dijkstra example</a>.</p>
- </div>
- <div class="section" id="bibliography">
- <h1><a class="toc-backref" href="#id24">Bibliography</a></h1>
- <table class="docutils citation" frame="void" id="cmms98a" rules="none">
- <colgroup><col class="label" /><col /></colgroup>
- <tbody valign="top">
- <tr><td class="label"><a class="fn-backref" href="#id1">[CMMS98a]</a></td><td>Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A
- Parallelization of Dijkstra's Shortest Path Algorithm. In
- <em>Mathematical Foundations of Computer Science (MFCS)</em>, volume 1450 of
- Lecture Notes in Computer Science, pages 722--731, 1998. Springer.</td></tr>
- </tbody>
- </table>
- <table class="docutils citation" frame="void" id="cmms98b" rules="none">
- <colgroup><col class="label" /><col /></colgroup>
- <tbody valign="top">
- <tr><td class="label"><a class="fn-backref" href="#id3">[CMMS98b]</a></td><td>Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
- Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical
- report, MPI-Informatik, 1998.</td></tr>
- </tbody>
- </table>
- <table class="docutils citation" frame="void" id="ms98" rules="none">
- <colgroup><col class="label" /><col /></colgroup>
- <tbody valign="top">
- <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
- shortest path algorithm. In <em>6th ESA</em>, LNCS. Springer, 1998.</td></tr>
- </tbody>
- </table>
- <hr class="docutils" />
- <p>Copyright (C) 2004, 2005, 2006, 2007, 2008 The Trustees of Indiana University.</p>
- <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
- </div>
- </div>
- <div class="footer">
- <hr class="footer" />
- Generated on: 2009-05-31 00:21 UTC.
- 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.
- </div>
- </body>
- </html>
|