boost/graph/dijkstra_shortest_paths.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 //
0010 //
0011 // Revision History:
0012 //   04 April 2001: Added named parameter variant. (Jeremy Siek)
0013 //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
0014 //
0015 #ifndef BOOST_GRAPH_DIJKSTRA_HPP
0016 #define BOOST_GRAPH_DIJKSTRA_HPP
0017
0018 #include <functional>
0019 #include <boost/limits.hpp>
0020 #include <boost/graph/named_function_params.hpp>
0021 #include <boost/graph/breadth_first_search.hpp>
0022 #include <boost/graph/relax.hpp>
0023 #include <boost/pending/indirect_cmp.hpp>
0024 #include <boost/graph/exception.hpp>
0025 #include <boost/graph/overloading.hpp>
0026 #include <boost/smart_ptr.hpp>
0027 #include <boost/graph/detail/d_ary_heap.hpp>
0028 #include <boost/graph/two_bit_color_map.hpp>
0029 #include <boost/graph/detail/mpi_include.hpp>
0030 #include <boost/property_map/property_map.hpp>
0031 #include <boost/property_map/vector_property_map.hpp>
0032 #include <boost/type_traits.hpp>
0033 #include <boost/concept/assert.hpp>
0034
0035 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
0036 #include <boost/pending/mutable_queue.hpp>
0037 #endif // BOOST_GRAPH_DIJKSTRA_TESTING
0038
0039 namespace boost
0040 {
0041
0042 /**
0043  * @brief Updates a particular value in a queue used by Dijkstra's
0044  * algorithm.
0045  *
0046  * This routine is called by Dijkstra's algorithm after it has
0047  * decreased the distance from the source vertex to the given @p
0048  * vertex. By default, this routine will just call @c
0049  * Q.update(vertex). However, other queues may provide more
0050  * specialized versions of this routine.
0051  *
0052  * @param Q             the queue that will be updated.
0053  * @param vertex        the vertex whose distance has been updated
0054  * @param old_distance  the previous distance to @p vertex
0055  */
0056 template < typename Buffer, typename Vertex, typename DistanceType >
0057 inline void dijkstra_queue_update(
0058     Buffer& Q, Vertex vertex, DistanceType old_distance)
0059 {
0060     (void)old_distance;
0061     Q.update(vertex);
0062 }
0063
0064 template < class Visitor, class Graph > struct DijkstraVisitorConcept
0065 {
0066     void constraints()
0067     {
0068         BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >));
0069         vis.initialize_vertex(u, g);
0070         vis.discover_vertex(u, g);
0071         vis.examine_vertex(u, g);
0072         vis.examine_edge(e, g);
0073         vis.edge_relaxed(e, g);
0074         vis.edge_not_relaxed(e, g);
0075         vis.finish_vertex(u, g);
0076     }
0077     Visitor vis;
0078     Graph g;
0079     typename graph_traits< Graph >::vertex_descriptor u;
0080     typename graph_traits< Graph >::edge_descriptor e;
0081 };
0082
0083 template < class Visitors = null_visitor >
0084 class dijkstra_visitor : public bfs_visitor< Visitors >
0085 {
0086 public:
0087     dijkstra_visitor() {}
0088     dijkstra_visitor(Visitors vis) : bfs_visitor< Visitors >(vis) {}
0089
0090     template < class Edge, class Graph > void edge_relaxed(Edge e, Graph& g)
0091     {
0092         invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
0093     }
0094     template < class Edge, class Graph > void edge_not_relaxed(Edge e, Graph& g)
0095     {
0096         invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
0097     }
0098
0099 private:
0100     template < class Edge, class Graph > void tree_edge(Edge u, Graph& g) {}
0101 };
0102 template < class Visitors >
0103 dijkstra_visitor< Visitors > make_dijkstra_visitor(Visitors vis)
0104 {
0105     return dijkstra_visitor< Visitors >(vis);
0106 }
0107 typedef dijkstra_visitor<> default_dijkstra_visitor;
0108
0109 namespace detail
0110 {
0111
0112     template < class UniformCostVisitor, class UpdatableQueue, class WeightMap,
0113         class PredecessorMap, class DistanceMap, class BinaryFunction,
0114         class BinaryPredicate >
0115     struct dijkstra_bfs_visitor
0116     {
0117         typedef typename property_traits< DistanceMap >::value_type D;
0118         typedef typename property_traits< WeightMap >::value_type W;
0119
0120         dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q,
0121             WeightMap w, PredecessorMap p, DistanceMap d,
0122             BinaryFunction combine, BinaryPredicate compare, D zero)
0123         : m_vis(vis)
0124         , m_Q(Q)
0125         , m_weight(w)
0126         , m_predecessor(p)
0127         , m_distance(d)
0128         , m_combine(combine)
0129         , m_compare(compare)
0130         , m_zero(zero)
0131         {
0132         }
0133
0134         template < class Edge, class Graph > void tree_edge(Edge e, Graph& g)
0135         {
0136             bool decreased = relax_target(e, g, m_weight, m_predecessor,
0137                 m_distance, m_combine, m_compare);
0138             if (decreased)
0139                 m_vis.edge_relaxed(e, g);
0140             else
0141                 m_vis.edge_not_relaxed(e, g);
0142         }
0143         template < class Edge, class Graph > void gray_target(Edge e, Graph& g)
0144         {
0145             D old_distance = get(m_distance, target(e, g));
0146
0147             bool decreased = relax_target(e, g, m_weight, m_predecessor,
0148                 m_distance, m_combine, m_compare);
0149             if (decreased)
0150             {
0151                 dijkstra_queue_update(m_Q, target(e, g), old_distance);
0152                 m_vis.edge_relaxed(e, g);
0153             }
0154             else
0155                 m_vis.edge_not_relaxed(e, g);
0156         }
0157
0158         template < class Vertex, class Graph >
0159         void initialize_vertex(Vertex u, Graph& g)
0160         {
0161             m_vis.initialize_vertex(u, g);
0162         }
0163         template < class Edge, class Graph > void non_tree_edge(Edge, Graph&) {}
0164         template < class Vertex, class Graph >
0165         void discover_vertex(Vertex u, Graph& g)
0166         {
0167             m_vis.discover_vertex(u, g);
0168         }
0169         template < class Vertex, class Graph >
0170         void examine_vertex(Vertex u, Graph& g)
0171         {
0172             m_vis.examine_vertex(u, g);
0173         }
0174         template < class Edge, class Graph > void examine_edge(Edge e, Graph& g)
0175         {
0176             // Test for negative-weight edges:
0177             //
0178             // Reasons that other comparisons do not work:
0179             //
0180             // m_compare(e_weight, D(0)):
0181             //    m_compare only needs to work on distances, not weights, and
0182             //    those types do not need to be the same (bug 8398,
0183             //    https://svn.boost.org/trac/boost/ticket/8398).
0184             // m_compare(m_combine(source_dist, e_weight), source_dist):
0185             //    if m_combine is project2nd (as in prim_minimum_spanning_tree),
0186             //    this test will claim that the edge weight is negative whenever
0187             //    the edge weight is less than source_dist, even if both of
0188             //    those are positive (bug 9012,
0189             //    https://svn.boost.org/trac/boost/ticket/9012).
0190             // m_compare(m_combine(e_weight, source_dist), source_dist):
0191             //    would fix project2nd issue, but documentation only requires
0192             //    that m_combine be able to take a distance and a weight (in
0193             //    that order) and return a distance.
0194
0195             // W e_weight = get(m_weight, e);
0196             // sd_plus_ew = source_dist + e_weight.
0197             // D sd_plus_ew = m_combine(source_dist, e_weight);
0198             // sd_plus_2ew = source_dist + 2 * e_weight.
0199             // D sd_plus_2ew = m_combine(sd_plus_ew, e_weight);
0200             // The test here is equivalent to e_weight < 0 if m_combine has a
0201             // cancellation law, but always returns false when m_combine is a
0202             // projection operator.
0203             if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero))
0204                 boost::throw_exception(negative_edge());
0205             // End of test for negative-weight edges.
0206
0207             m_vis.examine_edge(e, g);
0208         }
0209         template < class Edge, class Graph > void black_target(Edge, Graph&) {}
0210         template < class Vertex, class Graph >
0211         void finish_vertex(Vertex u, Graph& g)
0212         {
0213             m_vis.finish_vertex(u, g);
0214         }
0215
0216         UniformCostVisitor m_vis;
0217         UpdatableQueue& m_Q;
0218         WeightMap m_weight;
0219         PredecessorMap m_predecessor;
0220         DistanceMap m_distance;
0221         BinaryFunction m_combine;
0222         BinaryPredicate m_compare;
0223         D m_zero;
0224     };
0225
0226 } // namespace detail
0227
0228 namespace detail
0229 {
0230     template < class Graph, class IndexMap, class Value, bool KnownNumVertices >
0231     struct vertex_property_map_generator_helper
0232     {
0233     };
0234
0235     template < class Graph, class IndexMap, class Value >
0236     struct vertex_property_map_generator_helper< Graph, IndexMap, Value, true >
0237     {
0238         typedef boost::iterator_property_map< Value*, IndexMap > type;
0239         static type build(const Graph& g, const IndexMap& index,
0240             boost::scoped_array< Value >& array_holder)
0241         {
0242             array_holder.reset(new Value[num_vertices(g)]);
0243             std::fill(array_holder.get(), array_holder.get() + num_vertices(g),
0244                 Value());
0245             return make_iterator_property_map(array_holder.get(), index);
0246         }
0247     };
0248
0249     template < class Graph, class IndexMap, class Value >
0250     struct vertex_property_map_generator_helper< Graph, IndexMap, Value, false >
0251     {
0252         typedef boost::vector_property_map< Value, IndexMap > type;
0253         static type build(const Graph& g, const IndexMap& index,
0254             boost::scoped_array< Value >& array_holder)
0255         {
0256             return boost::make_vector_property_map< Value >(index);
0257         }
0258     };
0259
0260     template < class Graph, class IndexMap, class Value >
0261     struct vertex_property_map_generator
0262     {
0263         typedef boost::is_base_and_derived< boost::vertex_list_graph_tag,
0264             typename boost::graph_traits< Graph >::traversal_category >
0265             known_num_vertices;
0266         typedef vertex_property_map_generator_helper< Graph, IndexMap, Value,
0267             known_num_vertices::value >
0268             helper;
0269         typedef typename helper::type type;
0270         static type build(const Graph& g, const IndexMap& index,
0271             boost::scoped_array< Value >& array_holder)
0272         {
0273             return helper::build(g, index, array_holder);
0274         }
0275     };
0276 }
0277
0278 namespace detail
0279 {
0280     template < class Graph, class IndexMap, bool KnownNumVertices >
0281     struct default_color_map_generator_helper
0282     {
0283     };
0284
0285     template < class Graph, class IndexMap >
0286     struct default_color_map_generator_helper< Graph, IndexMap, true >
0287     {
0288         typedef boost::two_bit_color_map< IndexMap > type;
0289         static type build(const Graph& g, const IndexMap& index)
0290         {
0291             size_t nv = num_vertices(g);
0292             return boost::two_bit_color_map< IndexMap >(nv, index);
0293         }
0294     };
0295
0296     template < class Graph, class IndexMap >
0297     struct default_color_map_generator_helper< Graph, IndexMap, false >
0298     {
0299         typedef boost::vector_property_map< boost::two_bit_color_type,
0300             IndexMap >
0301             type;
0302         static type build(const Graph& g, const IndexMap& index)
0303         {
0304             return boost::make_vector_property_map< boost::two_bit_color_type >(
0305                 index);
0306         }
0307     };
0308
0309     template < class Graph, class IndexMap > struct default_color_map_generator
0310     {
0311         typedef boost::is_base_and_derived< boost::vertex_list_graph_tag,
0312             typename boost::graph_traits< Graph >::traversal_category >
0313             known_num_vertices;
0314         typedef default_color_map_generator_helper< Graph, IndexMap,
0315             known_num_vertices::value >
0316             helper;
0317         typedef typename helper::type type;
0318         static type build(const Graph& g, const IndexMap& index)
0319         {
0320             return helper::build(g, index);
0321         }
0322     };
0323 }
0324
0325 // Call breadth first search with default color map.
0326 template < class Graph, class SourceInputIter, class DijkstraVisitor,
0327     class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap,
0328     class Compare, class Combine, class DistZero >
0329 inline void dijkstra_shortest_paths_no_init(const Graph& g,
0330     SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor,
0331     DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare,
0332     Combine combine, DistZero zero, DijkstraVisitor vis)
0333 {
0334     typedef detail::default_color_map_generator< Graph, IndexMap >
0335         ColorMapHelper;
0336     typedef typename ColorMapHelper::type ColorMap;
0337     ColorMap color = ColorMapHelper::build(g, index_map);
0338     dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance,
0339         weight, index_map, compare, combine, zero, vis, color);
0340 }
0341
0342 // Call breadth first search with default color map.
0343 template < class Graph, class DijkstraVisitor, class PredecessorMap,
0344     class DistanceMap, class WeightMap, class IndexMap, class Compare,
0345     class Combine, class DistZero >
0346 inline void dijkstra_shortest_paths_no_init(const Graph& g,
0347     typename graph_traits< Graph >::vertex_descriptor s,
0348     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
0349     IndexMap index_map, Compare compare, Combine combine, DistZero zero,
0350     DijkstraVisitor vis)
0351 {
0352     dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
0353         weight, index_map, compare, combine, zero, vis);
0354 }
0355
0356 // Call breadth first search
0357 template < class Graph, class SourceInputIter, class DijkstraVisitor,
0358     class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap,
0359     class Compare, class Combine, class DistZero, class ColorMap >
0360 inline void dijkstra_shortest_paths_no_init(const Graph& g,
0361     SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor,
0362     DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare,
0363     Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color)
0364 {
0365     typedef indirect_cmp< DistanceMap, Compare > IndirectCmp;
0366     IndirectCmp icmp(distance, compare);
0367
0368     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0369
0370     // Now the default: use a d-ary heap
0371     boost::scoped_array< std::size_t > index_in_heap_map_holder;
0372     typedef detail::vertex_property_map_generator< Graph, IndexMap,
0373         std::size_t >
0374         IndexInHeapMapHelper;
0375     typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
0376     IndexInHeapMap index_in_heap
0377         = IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder);
0378     typedef d_ary_heap_indirect< Vertex, 4, IndexInHeapMap, DistanceMap,
0379         Compare >
0380         MutableQueue;
0381     MutableQueue Q(distance, index_in_heap, compare);
0382
0383     detail::dijkstra_bfs_visitor< DijkstraVisitor, MutableQueue, WeightMap,
0384         PredecessorMap, DistanceMap, Combine, Compare >
0385         bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
0386
0387     breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
0388 }
0389
0390 // Call breadth first search
0391 template < class Graph, class DijkstraVisitor, class PredecessorMap,
0392     class DistanceMap, class WeightMap, class IndexMap, class Compare,
0393     class Combine, class DistZero, class ColorMap >
0394 inline void dijkstra_shortest_paths_no_init(const Graph& g,
0395     typename graph_traits< Graph >::vertex_descriptor s,
0396     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
0397     IndexMap index_map, Compare compare, Combine combine, DistZero zero,
0398     DijkstraVisitor vis, ColorMap color)
0399 {
0400     dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
0401         weight, index_map, compare, combine, zero, vis, color);
0402 }
0403
0404 // Initialize distances and call breadth first search with default color map
0405 template < class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
0406     class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap,
0407     class Compare, class Combine, class DistInf, class DistZero, typename T,
0408     typename Tag, typename Base >
0409 inline void dijkstra_shortest_paths(const VertexListGraph& g,
0410     SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor,
0411     DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare,
0412     Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis,
0413     const bgl_named_params< T, Tag, Base >& BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0414         VertexListGraph, vertex_list_graph_tag))
0415 {
0416     boost::two_bit_color_map< IndexMap > color(num_vertices(g), index_map);
0417     dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight,
0418         index_map, compare, combine, inf, zero, vis, color);
0419 }
0420
0421 // Initialize distances and call breadth first search with default color map
0422 template < class VertexListGraph, class DijkstraVisitor, class PredecessorMap,
0423     class DistanceMap, class WeightMap, class IndexMap, class Compare,
0424     class Combine, class DistInf, class DistZero, typename T, typename Tag,
0425     typename Base >
0426 inline void dijkstra_shortest_paths(const VertexListGraph& g,
0427     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0428     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
0429     IndexMap index_map, Compare compare, Combine combine, DistInf inf,
0430     DistZero zero, DijkstraVisitor vis,
0431     const bgl_named_params< T, Tag, Base >& BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0432         VertexListGraph, vertex_list_graph_tag))
0433 {
0434     dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
0435         index_map, compare, combine, inf, zero, vis);
0436 }
0437
0438 // Initialize distances and call breadth first search
0439 template < class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
0440     class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap,
0441     class Compare, class Combine, class DistInf, class DistZero,
0442     class ColorMap >
0443 inline void dijkstra_shortest_paths(const VertexListGraph& g,
0444     SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor,
0445     DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare,
0446     Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis,
0447     ColorMap color)
0448 {
0449     typedef typename property_traits< ColorMap >::value_type ColorValue;
0450     typedef color_traits< ColorValue > Color;
0451     typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end;
0452     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0453     {
0454         vis.initialize_vertex(*ui, g);
0455         put(distance, *ui, inf);
0456         put(predecessor, *ui, *ui);
0457         put(color, *ui, Color::white());
0458     }
0459     for (SourceInputIter it = s_begin; it != s_end; ++it)
0460     {
0461         put(distance, *it, zero);
0462     }
0463
0464     dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance,
0465         weight, index_map, compare, combine, zero, vis, color);
0466 }
0467
0468 // Initialize distances and call breadth first search
0469 template < class VertexListGraph, class DijkstraVisitor, class PredecessorMap,
0470     class DistanceMap, class WeightMap, class IndexMap, class Compare,
0471     class Combine, class DistInf, class DistZero, class ColorMap >
0472 inline void dijkstra_shortest_paths(const VertexListGraph& g,
0473     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0474     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
0475     IndexMap index_map, Compare compare, Combine combine, DistInf inf,
0476     DistZero zero, DijkstraVisitor vis, ColorMap color)
0477 {
0478     dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
0479         index_map, compare, combine, inf, zero, vis, color);
0480 }
0481
0482 // Initialize distances and call breadth first search
0483 template < class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
0484     class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap,
0485     class Compare, class Combine, class DistInf, class DistZero >
0486 inline void dijkstra_shortest_paths(const VertexListGraph& g,
0487     SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor,
0488     DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare,
0489     Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis)
0490 {
0491     dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight,
0492         index_map, compare, combine, inf, zero, vis, no_named_parameters());
0493 }
0494
0495 // Initialize distances and call breadth first search
0496 template < class VertexListGraph, class DijkstraVisitor, class PredecessorMap,
0497     class DistanceMap, class WeightMap, class IndexMap, class Compare,
0498     class Combine, class DistInf, class DistZero >
0499 inline void dijkstra_shortest_paths(const VertexListGraph& g,
0500     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0501     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
0502     IndexMap index_map, Compare compare, Combine combine, DistInf inf,
0503     DistZero zero, DijkstraVisitor vis)
0504 {
0505     dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
0506         index_map, compare, combine, inf, zero, vis);
0507 }
0508
0509 namespace detail
0510 {
0511
0512     // Handle defaults for PredecessorMap and
0513     // Distance Compare, Combine, Inf and Zero
0514     template < class VertexListGraph, class DistanceMap, class WeightMap,
0515         class IndexMap, class Params >
0516     inline void dijkstra_dispatch2(const VertexListGraph& g,
0517         typename graph_traits< VertexListGraph >::vertex_descriptor s,
0518         DistanceMap distance, WeightMap weight, IndexMap index_map,
0519         const Params& params)
0520     {
0521         // Default for predecessor map
0522         dummy_property_map p_map;
0523
0524         typedef typename property_traits< DistanceMap >::value_type D;
0525         D inf = choose_param(get_param(params, distance_inf_t()),
0526             (std::numeric_limits< D >::max)());
0527
0528         dijkstra_shortest_paths(g, s,
0529             choose_param(get_param(params, vertex_predecessor), p_map),
0530             distance, weight, index_map,
0531             choose_param(
0532                 get_param(params, distance_compare_t()), std::less< D >()),
0533             choose_param(
0534                 get_param(params, distance_combine_t()), std::plus< D >()),
0535             inf, choose_param(get_param(params, distance_zero_t()), D()),
0536             choose_param(get_param(params, graph_visitor),
0537                 make_dijkstra_visitor(null_visitor())),
0538             params);
0539     }
0540
0541     template < class VertexListGraph, class DistanceMap, class WeightMap,
0542         class IndexMap, class Params >
0543     inline void dijkstra_dispatch1(const VertexListGraph& g,
0544         typename graph_traits< VertexListGraph >::vertex_descriptor s,
0545         DistanceMap distance, WeightMap weight, IndexMap index_map,
0546         const Params& params)
0547     {
0548         // Default for distance map
0549         typedef typename property_traits< WeightMap >::value_type D;
0550         typename std::vector< D >::size_type n
0551             = is_default_param(distance) ? num_vertices(g) : 1;
0552         std::vector< D > distance_map(n);
0553
0554         detail::dijkstra_dispatch2(g, s,
0555             choose_param(distance,
0556                 make_iterator_property_map(
0557                     distance_map.begin(), index_map, distance_map[0])),
0558             weight, index_map, params);
0559     }
0560 } // namespace detail
0561
0562 // Named Parameter Variant
0563 template < class VertexListGraph, class Param, class Tag, class Rest >
0564 inline void dijkstra_shortest_paths(const VertexListGraph& g,
0565     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0566     const bgl_named_params< Param, Tag, Rest >& params)
0567 {
0568     // Default for edge weight and vertex index map is to ask for them
0569     // from the graph.  Default for the visitor is null_visitor.
0570     detail::dijkstra_dispatch1(g, s, get_param(params, vertex_distance),
0571         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
0572         choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
0573         params);
0574 }
0575
0576 } // namespace boost
0577
0578 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/dijkstra_shortest_paths.hpp>)
0579
0580 #endif // BOOST_GRAPH_DIJKSTRA_HPP