boost_1_45_0/libs/graph_parallel/doc/dijkstra_shortest_paths.rst - nest-learning-thermostat/5.0/boost - Git at Google

 .. 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)

 ==============================================
 |Logo| Dijkstra's Single-Source Shortest Paths
 ==============================================

 ::

   // 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);

 The ``dijkstra_shortest_paths()`` 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 ``dijkstra_shortest_paths()``
 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 `sequential Dijkstra implementation`_ for additional
 details. The best-performing implementation for most cases is the
 `Delta-Stepping algorithm`_; however, one can also employ the more
 conservative `Crauser et al.'s algorithm`_ or the simlistic  `Eager
 Dijkstra's algorithm`_.

 .. contents::

 Where Defined
 -------------
 <``boost/graph/dijkstra_shortest_paths.hpp``>

 Parameters
 ----------

 All parameters of the `sequential Dijkstra implementation`_ are
 supported and have essentially the same meaning. The distributed
 Dijkstra implementations introduce a new parameter that allows one to
 select `Eager Dijkstra's algorithm`_ and control the amount of work it
 performs. Only differences and new parameters are documented here.

 IN: ``Graph& g``
   The graph type must be a model of `Distributed Graph`_.


 IN: ``vertex_descriptor s``
   The start vertex must be the same in every process.


 OUT: ``predecessor_map(PredecessorMap p_map)``
   The predecessor map must be a `Distributed Property Map`_ or
   ``dummy_property_map``, although only the local portions of the map
   will be written.

   **Default:** ``dummy_property_map``


 UTIL/OUT: ``distance_map(DistanceMap d_map)``
   The distance map must be either a `Distributed Property Map`_ or
   ``dummy_property_map``. It will be given the ``vertex_distance``
   role.


 IN: ``visitor(DijkstraVisitor vis)``
   The visitor must be a distributed Dijkstra visitor. The suble differences
   between sequential and distributed Dijkstra visitors are discussed in the
   section `Visitor Event Points`_.


 UTIL/OUT: ``color_map(ColorMap color)``
   The color map must be a `Distributed Property Map`_ with the same
   process group as the graph ``g`` whose colors must monotonically
   darken (white -> gray -> black). The default value is a distributed
   ``iterator_property_map`` created from a ``std::vector`` of
   ``default_color_type``.


 IN: ``lookahead(distance_type look)``

   When this parameter is supplied, the implementation will use the
   `Eager Dijkstra's algorithm`_ 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.

   The type ``distance_type`` is the value type of the ``DistanceMap``
   property map. It is a nonnegative value specifying how far ahead
   Dijkstra's algorithm may process values.

   **Default:** no value (lookahead is not employed; uses `Crauser et
   al.'s algorithm`_).

 Visitor Event Points
 --------------------
 The `Dijkstra Visitor`_ concept defines 7 event points that will be
 triggered by the `sequential Dijkstra implementation`_. 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.

 ``initialize_vertex(s, g)``
   This will be invoked by every process for each local vertex.


 ``discover_vertex(u, g)``
   This will be invoked each type a process discovers a new vertex
   ``u``. Due to incomplete information in distributed property maps,
   this event may be triggered many times for the same vertex ``u``.


 ``examine_vertex(u, g)``
   This will be invoked by the process owning the vertex ``u``. This
   event may be invoked multiple times for the same vertex when the
   graph contains negative edges or lookahead is employed.


 ``examine_edge(e, g)``
   This will be invoked by the process owning the source vertex of
   ``e``. As with ``examine_vertex``, this event may be invoked
   multiple times for the same edge.


 ``edge_relaxed(e, g)``
   Similar to ``examine_edge``, this will be invoked by the process
   owning the source vertex and may be invoked multiple times (even
   without lookahead or negative edges).


 ``edge_not_relaxed(e, g)``
   Similar to ``edge_relaxed``. Some ``edge_not_relaxed`` events that
   would be triggered by sequential Dijkstra's will become
   ``edge_relaxed`` events in distributed Dijkstra's algorithm.


 ``finish_vertex(e, g)``
   See documentation for ``examine_vertex``. Note that a "finished"
   vertex is not necessarily finished if lookahead is permitted or
   negative edges exist in the graph.


 Crauser et al.'s algorithm
 --------------------------

 ::

   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);
   }

 The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer,
 and Sanders [CMMS98a]_ 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.

 This algorithm is used by default in distributed
 ``dijkstra_shortest_paths()``.

 Where Defined
 ~~~~~~~~~~~~~
 <``boost/graph/distributed/crauser_et_al_shortest_paths.hpp``>

 Complexity
 ~~~~~~~~~~
 This algorithm performs *O(V log V)* work in *d + 1* BSP supersteps,
 where *d* is at most *O(V)* but is generally much smaller. On directed
 Erdos-Renyi graphs with edge weights in [0, 1), the expected number of
 supersteps *d* is *O(n^(1/3))* with high probability.

 Performance
 ~~~~~~~~~~~
 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 *[0, 1)*.

 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4
   :align: left
 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1

 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4
   :align: left
 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1


 Eager Dijkstra's algorithm
 --------------------------

 ::

   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);
   }

 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 [CMMS98b]_ and [MS98]_.

 This algorithm will be used by ``dijkstra_shortest_paths()`` when it
 is provided with a lookahead value.

 Where Defined
 ~~~~~~~~~~~~~
 <``boost/graph/distributed/eager_dijkstra_shortest_paths.hpp``>

 Complexity
 ~~~~~~~~~~
 This algorithm performs *O(V log V)* work in *d
 + 1* BSP supersteps, where *d* is at most *O(V)* 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.

 Performance
 ~~~~~~~~~~~
 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 *[0, 1)* and a constant lookahead of 0.1.

 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5
   :align: left
 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5&speedup=1

 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5
   :align: left
 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5&speedup=1

 Delta-Stepping algorithm
 --------------------------

 ::

   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)
     }

   } } }


 The delta-stepping algorithm [MS98]_ is another variant of the parallel
 Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a
 lookahead (``delta``) 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.

 The lookahead value ``delta`` determines how large each of the
 "buckets" within the delta-stepping queue will be, where the ith
 bucket contains edges within tentative distances between ``delta``*i
 and ``delta``*(i+1). ``delta`` must be a positive value. When omitted,
 ``delta`` will be set to the maximum edge weight divided by the
 maximum degree.

 Where Defined
 ~~~~~~~~~~~~~
 <``boost/graph/distributed/delta_stepping_shortest_paths.hpp``>

 Example
 -------
 See the separate `Dijkstra example`_.


 Bibliography
 ------------

 .. [CMMS98a] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A
   Parallelization of Dijkstra's Shortest Path Algorithm. In
   *Mathematical Foundations of Computer Science (MFCS)*, volume 1450 of
   Lecture Notes in Computer Science, pages 722--731, 1998. Springer.

 .. [CMMS98b] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
   Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical
   report, MPI-Informatik, 1998.

 .. [MS98] Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel
   shortest path algorithm. In *6th ESA*, LNCS. Springer, 1998.

 -----------------------------------------------------------------------------

 Copyright (C) 2004, 2005, 2006, 2007, 2008 The Trustees of Indiana University.

 Authors: Douglas Gregor and Andrew Lumsdaine

 .. |Logo| image:: pbgl-logo.png
             :align: middle
             :alt: Parallel BGL
             :target: http://www.osl.iu.edu/research/pbgl

 .. _sequential Dijkstra implementation: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
 .. _distributed breadth-first search: breadth_first_search.html
 .. _Distributed Graph: DistributedGraph.html
 .. _Distributed Property Map: distributed_property_map.html
 .. _Dijkstra Visitor: http://www.boost.org/libs/graph/doc/DijkstraVisitor.html
 .. _Dijkstra example: dijkstra_example.html
	.. 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)

	==============================================
	\|Logo\| Dijkstra's Single-Source Shortest Paths
	==============================================

	::

	// 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);

	The ``dijkstra_shortest_paths()`` 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 ``dijkstra_shortest_paths()``
	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 `sequential Dijkstra implementation`_ for additional
	details. The best-performing implementation for most cases is the
	`Delta-Stepping algorithm`_; however, one can also employ the more
	conservative `Crauser et al.'s algorithm`_ or the simlistic `Eager
	Dijkstra's algorithm`_.

	.. contents::

	Where Defined
	-------------
	<``boost/graph/dijkstra_shortest_paths.hpp``>

	Parameters
	----------

	All parameters of the `sequential Dijkstra implementation`_ are
	supported and have essentially the same meaning. The distributed
	Dijkstra implementations introduce a new parameter that allows one to
	select `Eager Dijkstra's algorithm`_ and control the amount of work it
	performs. Only differences and new parameters are documented here.

	IN: ``Graph& g``
	The graph type must be a model of `Distributed Graph`_.


	IN: ``vertex_descriptor s``
	The start vertex must be the same in every process.


	OUT: ``predecessor_map(PredecessorMap p_map)``
	The predecessor map must be a `Distributed Property Map`_ or
	``dummy_property_map``, although only the local portions of the map
	will be written.

	Default: ``dummy_property_map``


	UTIL/OUT: ``distance_map(DistanceMap d_map)``
	The distance map must be either a `Distributed Property Map`_ or
	``dummy_property_map``. It will be given the ``vertex_distance``
	role.


	IN: ``visitor(DijkstraVisitor vis)``
	The visitor must be a distributed Dijkstra visitor. The suble differences
	between sequential and distributed Dijkstra visitors are discussed in the
	section `Visitor Event Points`_.


	UTIL/OUT: ``color_map(ColorMap color)``
	The color map must be a `Distributed Property Map`_ with the same
	process group as the graph ``g`` whose colors must monotonically
	darken (white -> gray -> black). The default value is a distributed
	``iterator_property_map`` created from a ``std::vector`` of
	``default_color_type``.


	IN: ``lookahead(distance_type look)``

	When this parameter is supplied, the implementation will use the
	`Eager Dijkstra's algorithm`_ 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.

	The type ``distance_type`` is the value type of the ``DistanceMap``
	property map. It is a nonnegative value specifying how far ahead
	Dijkstra's algorithm may process values.

	Default: no value (lookahead is not employed; uses `Crauser et
	al.'s algorithm`_).

	Visitor Event Points
	--------------------
	The `Dijkstra Visitor`_ concept defines 7 event points that will be
	triggered by the `sequential Dijkstra implementation`_. 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.

	``initialize_vertex(s, g)``
	This will be invoked by every process for each local vertex.


	``discover_vertex(u, g)``
	This will be invoked each type a process discovers a new vertex
	``u``. Due to incomplete information in distributed property maps,
	this event may be triggered many times for the same vertex ``u``.


	``examine_vertex(u, g)``
	This will be invoked by the process owning the vertex ``u``. This
	event may be invoked multiple times for the same vertex when the
	graph contains negative edges or lookahead is employed.


	``examine_edge(e, g)``
	This will be invoked by the process owning the source vertex of
	``e``. As with ``examine_vertex``, this event may be invoked
	multiple times for the same edge.


	``edge_relaxed(e, g)``
	Similar to ``examine_edge``, this will be invoked by the process
	owning the source vertex and may be invoked multiple times (even
	without lookahead or negative edges).


	``edge_not_relaxed(e, g)``
	Similar to ``edge_relaxed``. Some ``edge_not_relaxed`` events that
	would be triggered by sequential Dijkstra's will become
	``edge_relaxed`` events in distributed Dijkstra's algorithm.


	``finish_vertex(e, g)``
	See documentation for ``examine_vertex``. Note that a "finished"
	vertex is not necessarily finished if lookahead is permitted or
	negative edges exist in the graph.


	Crauser et al.'s algorithm
	--------------------------

	::

	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);
	}

	The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer,
	and Sanders [CMMS98a]_ 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.

	This algorithm is used by default in distributed
	``dijkstra_shortest_paths()``.

	Where Defined
	~~~~~~~~~~~~~
	<``boost/graph/distributed/crauser_et_al_shortest_paths.hpp``>

	Complexity
	~~~~~~~~~~
	This algorithm performs O(V log V) work in d + 1 BSP supersteps,
	where d is at most O(V) but is generally much smaller. On directed
	Erdos-Renyi graphs with edge weights in [0, 1), the expected number of
	supersteps d is O(n^(1/3)) with high probability.

	Performance
	~~~~~~~~~~~
	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 [0, 1).

	.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4
	:align: left
	.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1

	.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4
	:align: left
	.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1


	Eager Dijkstra's algorithm
	--------------------------

	::

	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);
	}

	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 [CMMS98b]_ and [MS98]_.

	This algorithm will be used by ``dijkstra_shortest_paths()`` when it
	is provided with a lookahead value.

	Where Defined
	~~~~~~~~~~~~~
	<``boost/graph/distributed/eager_dijkstra_shortest_paths.hpp``>

	Complexity
	~~~~~~~~~~
	This algorithm performs O(V log V) work in *d
	+ 1* BSP supersteps, where d is at most O(V) 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.

	Performance
	~~~~~~~~~~~
	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 [0, 1) and a constant lookahead of 0.1.

	.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5
	:align: left
	.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5&speedup=1

	.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5
	:align: left
	.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5&speedup=1

	Delta-Stepping algorithm
	--------------------------

	::

	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)
	}

	} } }


	The delta-stepping algorithm [MS98]_ is another variant of the parallel
	Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a
	lookahead (``delta``) 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.

	The lookahead value ``delta`` determines how large each of the
	"buckets" within the delta-stepping queue will be, where the ith
	bucket contains edges within tentative distances between ``delta``*i
	and ``delta``*(i+1). ``delta`` must be a positive value. When omitted,
	``delta`` will be set to the maximum edge weight divided by the
	maximum degree.

	Where Defined
	~~~~~~~~~~~~~
	<``boost/graph/distributed/delta_stepping_shortest_paths.hpp``>

	Example
	-------
	See the separate `Dijkstra example`_.


	Bibliography
	------------

	.. [CMMS98a] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A
	Parallelization of Dijkstra's Shortest Path Algorithm. In
	Mathematical Foundations of Computer Science (MFCS), volume 1450 of
	Lecture Notes in Computer Science, pages 722--731, 1998. Springer.

	.. [CMMS98b] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
	Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical
	report, MPI-Informatik, 1998.

	.. [MS98] Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel
	shortest path algorithm. In 6th ESA, LNCS. Springer, 1998.

	-----------------------------------------------------------------------------

	Copyright (C) 2004, 2005, 2006, 2007, 2008 The Trustees of Indiana University.

	Authors: Douglas Gregor and Andrew Lumsdaine

	.. \|Logo\| image:: pbgl-logo.png
	:align: middle
	:alt: Parallel BGL
	:target: http://www.osl.iu.edu/research/pbgl

	.. _sequential Dijkstra implementation: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
	.. _distributed breadth-first search: breadth_first_search.html
	.. _Distributed Graph: DistributedGraph.html
	.. _Distributed Property Map: distributed_property_map.html
	.. _Dijkstra Visitor: http://www.boost.org/libs/graph/doc/DijkstraVisitor.html
	.. _Dijkstra example: dijkstra_example.html