boost/graph/dijkstra_shortest_paths.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9 //
  10 //
  11 // Revision History:
  12 //   04 April 2001: Added named parameter variant. (Jeremy Siek)
  13 //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
  14 //
  15 #ifndef BOOST_GRAPH_DIJKSTRA_HPP
  16 #define BOOST_GRAPH_DIJKSTRA_HPP
  17
  18 #include <functional>
  19 #include <boost/limits.hpp>
  20 #include <boost/graph/named_function_params.hpp>
  21 #include <boost/graph/breadth_first_search.hpp>
  22 #include <boost/graph/relax.hpp>
  23 #include <boost/pending/indirect_cmp.hpp>
  24 #include <boost/graph/exception.hpp>
  25 #include <boost/pending/relaxed_heap.hpp>
  26 #include <boost/graph/overloading.hpp>
  27 #include <boost/smart_ptr.hpp>
  28 #include <boost/graph/detail/d_ary_heap.hpp>
  29 #include <boost/graph/two_bit_color_map.hpp>
  30 #include <boost/property_map/property_map.hpp>
  31 #include <boost/property_map/vector_property_map.hpp>
  32 #include <boost/type_traits.hpp>
  33 #include <boost/concept/assert.hpp>
  34
  35 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
  36 #  include <boost/pending/mutable_queue.hpp>
  37 #endif // BOOST_GRAPH_DIJKSTRA_TESTING
  38
  39 namespace boost {
  40
  41   /**
  42    * @brief Updates a particular value in a queue used by Dijkstra's
  43    * algorithm.
  44    *
  45    * This routine is called by Dijkstra's algorithm after it has
  46    * decreased the distance from the source vertex to the given @p
  47    * vertex. By default, this routine will just call @c
  48    * Q.update(vertex). However, other queues may provide more
  49    * specialized versions of this routine.
  50    *
  51    * @param Q             the queue that will be updated.
  52    * @param vertex        the vertex whose distance has been updated
  53    * @param old_distance  the previous distance to @p vertex
  54    */
  55   template<typename Buffer, typename Vertex, typename DistanceType>
  56   inline void
  57   dijkstra_queue_update(Buffer& Q, Vertex vertex, DistanceType old_distance)
  58   {
  59     (void)old_distance;
  60     Q.update(vertex);
  61   }
  62
  63 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
  64   // This is a misnomer now: it now just refers to the "default heap", which is
  65   // currently d-ary (d=4) but can be changed by a #define.
  66   static bool dijkstra_relaxed_heap = true;
  67 #endif
  68
  69   template <class Visitor, class Graph>
  70   struct DijkstraVisitorConcept {
  71     void constraints() {
  72       BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
  73       vis.initialize_vertex(u, g);
  74       vis.discover_vertex(u, g);
  75       vis.examine_vertex(u, g);
  76       vis.examine_edge(e, g);
  77       vis.edge_relaxed(e, g);
  78       vis.edge_not_relaxed(e, g);
  79       vis.finish_vertex(u, g);
  80     }
  81     Visitor vis;
  82     Graph g;
  83     typename graph_traits<Graph>::vertex_descriptor u;
  84     typename graph_traits<Graph>::edge_descriptor e;
  85   };
  86
  87   template <class Visitors = null_visitor>
  88   class dijkstra_visitor : public bfs_visitor<Visitors> {
  89   public:
  90     dijkstra_visitor() { }
  91     dijkstra_visitor(Visitors vis)
  92       : bfs_visitor<Visitors>(vis) { }
  93
  94     template <class Edge, class Graph>
  95     void edge_relaxed(Edge e, Graph& g) {
  96       invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
  97     }
  98     template <class Edge, class Graph>
  99     void edge_not_relaxed(Edge e, Graph& g) {
 100       invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
 101     }
 102   private:
 103     template <class Edge, class Graph>
 104     void tree_edge(Edge u, Graph& g) { }
 105   };
 106   template <class Visitors>
 107   dijkstra_visitor<Visitors>
 108   make_dijkstra_visitor(Visitors vis) {
 109     return dijkstra_visitor<Visitors>(vis);
 110   }
 111   typedef dijkstra_visitor<> default_dijkstra_visitor;
 112
 113   namespace detail {
 114
 115     template <class UniformCostVisitor, class UpdatableQueue,
 116       class WeightMap, class PredecessorMap, class DistanceMap,
 117       class BinaryFunction, class BinaryPredicate>
 118     struct dijkstra_bfs_visitor
 119     {
 120       typedef typename property_traits<DistanceMap>::value_type D;
 121       typedef typename property_traits<WeightMap>::value_type W;
 122
 123       dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q,
 124                            WeightMap w, PredecessorMap p, DistanceMap d,
 125                            BinaryFunction combine, BinaryPredicate compare,
 126                            D zero)
 127         : m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d),
 128           m_combine(combine), m_compare(compare), m_zero(zero)  { }
 129
 130       template <class Edge, class Graph>
 131       void tree_edge(Edge e, Graph& g) {
 132         bool decreased = relax(e, g, m_weight, m_predecessor, m_distance,
 133                                m_combine, m_compare);
 134         if (decreased)
 135           m_vis.edge_relaxed(e, g);
 136         else
 137           m_vis.edge_not_relaxed(e, g);
 138       }
 139       template <class Edge, class Graph>
 140       void gray_target(Edge e, Graph& g) {
 141         D old_distance = get(m_distance, target(e, g));
 142
 143         bool decreased = relax(e, g, m_weight, m_predecessor, m_distance,
 144                                m_combine, m_compare);
 145         if (decreased) {
 146           dijkstra_queue_update(m_Q, target(e, g), old_distance);
 147           m_vis.edge_relaxed(e, g);
 148         } else
 149           m_vis.edge_not_relaxed(e, g);
 150       }
 151
 152       template <class Vertex, class Graph>
 153       void initialize_vertex(Vertex u, Graph& g)
 154         { m_vis.initialize_vertex(u, g); }
 155       template <class Edge, class Graph>
 156       void non_tree_edge(Edge, Graph&) { }
 157       template <class Vertex, class Graph>
 158       void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); }
 159       template <class Vertex, class Graph>
 160       void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
 161       template <class Edge, class Graph>
 162       void examine_edge(Edge e, Graph& g) {
 163         // Test for negative-weight edges:
 164         //
 165         // Reasons that other comparisons do not work:
 166         //
 167         // m_compare(e_weight, D(0)):
 168         //    m_compare only needs to work on distances, not weights, and those
 169         //    types do not need to be the same (bug 8398,
 170         //    https://svn.boost.org/trac/boost/ticket/8398).
 171         // m_compare(m_combine(source_dist, e_weight), source_dist):
 172         //    if m_combine is project2nd (as in prim_minimum_spanning_tree),
 173         //    this test will claim that the edge weight is negative whenever
 174         //    the edge weight is less than source_dist, even if both of those
 175         //    are positive (bug 9012,
 176         //    https://svn.boost.org/trac/boost/ticket/9012).
 177         // m_compare(m_combine(e_weight, source_dist), source_dist):
 178         //    would fix project2nd issue, but documentation only requires that
 179         //    m_combine be able to take a distance and a weight (in that order)
 180         //    and return a distance.
 181
 182         // W e_weight = get(m_weight, e);
 183         // sd_plus_ew = source_dist + e_weight.
 184         // D sd_plus_ew = m_combine(source_dist, e_weight);
 185         // sd_plus_2ew = source_dist + 2 * e_weight.
 186         // D sd_plus_2ew = m_combine(sd_plus_ew, e_weight);
 187         // The test here is equivalent to e_weight < 0 if m_combine has a
 188         // cancellation law, but always returns false when m_combine is a
 189         // projection operator.
 190         if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero))
 191             boost::throw_exception(negative_edge());
 192         // End of test for negative-weight edges.
 193
 194         m_vis.examine_edge(e, g);
 195
 196       }
 197       template <class Edge, class Graph>
 198       void black_target(Edge, Graph&) { }
 199       template <class Vertex, class Graph>
 200       void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); }
 201
 202       UniformCostVisitor m_vis;
 203       UpdatableQueue& m_Q;
 204       WeightMap m_weight;
 205       PredecessorMap m_predecessor;
 206       DistanceMap m_distance;
 207       BinaryFunction m_combine;
 208       BinaryPredicate m_compare;
 209       D m_zero;
 210     };
 211
 212   } // namespace detail
 213
 214   namespace detail {
 215     template <class Graph, class IndexMap, class Value, bool KnownNumVertices>
 216     struct vertex_property_map_generator_helper {};
 217
 218     template <class Graph, class IndexMap, class Value>
 219     struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> {
 220       typedef boost::iterator_property_map<Value*, IndexMap> type;
 221       static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
 222         array_holder.reset(new Value[num_vertices(g)]);
 223         std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value());
 224         return make_iterator_property_map(array_holder.get(), index);
 225       }
 226     };
 227
 228     template <class Graph, class IndexMap, class Value>
 229     struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> {
 230       typedef boost::vector_property_map<Value, IndexMap> type;
 231       static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
 232         return boost::make_vector_property_map<Value>(index);
 233       }
 234     };
 235
 236     template <class Graph, class IndexMap, class Value>
 237     struct vertex_property_map_generator {
 238       typedef boost::is_base_and_derived<
 239                 boost::vertex_list_graph_tag,
 240                 typename boost::graph_traits<Graph>::traversal_category>
 241               known_num_vertices;
 242       typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper;
 243       typedef typename helper::type type;
 244       static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
 245         return helper::build(g, index, array_holder);
 246       }
 247     };
 248   }
 249
 250   namespace detail {
 251     template <class Graph, class IndexMap, bool KnownNumVertices>
 252     struct default_color_map_generator_helper {};
 253
 254     template <class Graph, class IndexMap>
 255     struct default_color_map_generator_helper<Graph, IndexMap, true> {
 256       typedef boost::two_bit_color_map<IndexMap> type;
 257       static type build(const Graph& g, const IndexMap& index) {
 258         size_t nv = num_vertices(g);
 259         return boost::two_bit_color_map<IndexMap>(nv, index);
 260       }
 261     };
 262
 263     template <class Graph, class IndexMap>
 264     struct default_color_map_generator_helper<Graph, IndexMap, false> {
 265       typedef boost::vector_property_map<boost::two_bit_color_type, IndexMap> type;
 266       static type build(const Graph& g, const IndexMap& index) {
 267         return boost::make_vector_property_map<boost::two_bit_color_type>(index);
 268       }
 269     };
 270
 271     template <class Graph, class IndexMap>
 272     struct default_color_map_generator {
 273       typedef boost::is_base_and_derived<
 274                 boost::vertex_list_graph_tag,
 275                 typename boost::graph_traits<Graph>::traversal_category>
 276               known_num_vertices;
 277       typedef default_color_map_generator_helper<Graph, IndexMap, known_num_vertices::value> helper;
 278       typedef typename helper::type type;
 279       static type build(const Graph& g, const IndexMap& index) {
 280         return helper::build(g, index);
 281       }
 282     };
 283   }
 284
 285   // Call breadth first search with default color map.
 286   template <class Graph, class SourceInputIter, class DijkstraVisitor,
 287             class PredecessorMap, class DistanceMap,
 288             class WeightMap, class IndexMap, class Compare, class Combine,
 289             class DistZero>
 290   inline void
 291   dijkstra_shortest_paths_no_init
 292     (const Graph& g,
 293      SourceInputIter s_begin, SourceInputIter s_end,
 294      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 295      IndexMap index_map,
 296      Compare compare, Combine combine, DistZero zero,
 297      DijkstraVisitor vis)
 298   {
 299     typedef
 300       detail::default_color_map_generator<Graph, IndexMap>
 301       ColorMapHelper;
 302     typedef typename ColorMapHelper::type ColorMap;
 303     ColorMap color =
 304       ColorMapHelper::build(g, index_map);
 305     dijkstra_shortest_paths_no_init( g, s_begin, s_end, predecessor, distance, weight,
 306       index_map, compare, combine, zero, vis,
 307         color);
 308   }
 309
 310   // Call breadth first search with default color map.
 311   template <class Graph, class DijkstraVisitor,
 312             class PredecessorMap, class DistanceMap,
 313             class WeightMap, class IndexMap, class Compare, class Combine,
 314             class DistZero>
 315   inline void
 316   dijkstra_shortest_paths_no_init
 317     (const Graph& g,
 318      typename graph_traits<Graph>::vertex_descriptor s,
 319      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 320      IndexMap index_map,
 321      Compare compare, Combine combine, DistZero zero,
 322      DijkstraVisitor vis)
 323   {
 324     dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
 325                                     weight, index_map, compare, combine, zero,
 326                                     vis);
 327   }
 328
 329   // Call breadth first search
 330   template <class Graph, class SourceInputIter, class DijkstraVisitor,
 331             class PredecessorMap, class DistanceMap,
 332             class WeightMap, class IndexMap, class Compare, class Combine,
 333             class DistZero, class ColorMap>
 334   inline void
 335   dijkstra_shortest_paths_no_init
 336     (const Graph& g,
 337      SourceInputIter s_begin, SourceInputIter s_end,
 338      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 339      IndexMap index_map,
 340      Compare compare, Combine combine, DistZero zero,
 341      DijkstraVisitor vis, ColorMap color)
 342   {
 343     typedef indirect_cmp<DistanceMap, Compare> IndirectCmp;
 344     IndirectCmp icmp(distance, compare);
 345
 346     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 347
 348 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
 349     if (!dijkstra_relaxed_heap) {
 350       typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap>
 351         MutableQueue;
 352
 353       MutableQueue Q(num_vertices(g), icmp, index_map);
 354       detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
 355         PredecessorMap, DistanceMap, Combine, Compare>
 356       bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
 357
 358       breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
 359       return;
 360     }
 361 #endif // BOOST_GRAPH_DIJKSTRA_TESTING
 362
 363 #ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
 364     typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue;
 365     MutableQueue Q(num_vertices(g), icmp, index_map);
 366 #else // Now the default: use a d-ary heap
 367       boost::scoped_array<std::size_t> index_in_heap_map_holder;
 368       typedef
 369         detail::vertex_property_map_generator<Graph, IndexMap, std::size_t>
 370         IndexInHeapMapHelper;
 371       typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
 372       IndexInHeapMap index_in_heap =
 373         IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder);
 374       typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>
 375         MutableQueue;
 376       MutableQueue Q(distance, index_in_heap, compare);
 377 #endif // Relaxed heap
 378
 379     detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
 380       PredecessorMap, DistanceMap, Combine, Compare>
 381         bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
 382
 383     breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
 384   }
 385
 386   // Call breadth first search
 387   template <class Graph, class DijkstraVisitor,
 388             class PredecessorMap, class DistanceMap,
 389             class WeightMap, class IndexMap, class Compare, class Combine,
 390             class DistZero, class ColorMap>
 391   inline void
 392   dijkstra_shortest_paths_no_init
 393     (const Graph& g,
 394      typename graph_traits<Graph>::vertex_descriptor s,
 395      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 396      IndexMap index_map,
 397      Compare compare, Combine combine, DistZero zero,
 398      DijkstraVisitor vis, ColorMap color)
 399   {
 400     dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
 401                                     weight, index_map, compare, combine,
 402                                     zero, vis, color);
 403   }
 404
 405   // Initialize distances and call breadth first search with default color map
 406   template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
 407             class PredecessorMap, class DistanceMap,
 408             class WeightMap, class IndexMap, class Compare, class Combine,
 409             class DistInf, class DistZero, typename T, typename Tag,
 410             typename Base>
 411   inline void
 412   dijkstra_shortest_paths
 413     (const VertexListGraph& g,
 414      SourceInputIter s_begin, SourceInputIter s_end,
 415      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 416      IndexMap index_map,
 417      Compare compare, Combine combine, DistInf inf, DistZero zero,
 418      DijkstraVisitor vis,
 419      const bgl_named_params<T, Tag, Base>&
 420      BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag))
 421   {
 422     boost::two_bit_color_map<IndexMap> color(num_vertices(g), index_map);
 423     dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight,
 424                             index_map, compare, combine, inf, zero, vis,
 425                             color);
 426   }
 427
 428   // Initialize distances and call breadth first search with default color map
 429   template <class VertexListGraph, class DijkstraVisitor,
 430             class PredecessorMap, class DistanceMap,
 431             class WeightMap, class IndexMap, class Compare, class Combine,
 432             class DistInf, class DistZero, typename T, typename Tag,
 433             typename Base>
 434   inline void
 435   dijkstra_shortest_paths
 436     (const VertexListGraph& g,
 437      typename graph_traits<VertexListGraph>::vertex_descriptor s,
 438      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 439      IndexMap index_map,
 440      Compare compare, Combine combine, DistInf inf, DistZero zero,
 441      DijkstraVisitor vis,
 442      const bgl_named_params<T, Tag, Base>&
 443      BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag))
 444   {
 445     dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
 446                             index_map, compare, combine, inf, zero, vis);
 447   }
 448
 449   // Initialize distances and call breadth first search
 450   template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
 451             class PredecessorMap, class DistanceMap,
 452             class WeightMap, class IndexMap, class Compare, class Combine,
 453             class DistInf, class DistZero, class ColorMap>
 454   inline void
 455   dijkstra_shortest_paths
 456     (const VertexListGraph& g,
 457      SourceInputIter s_begin, SourceInputIter s_end,
 458      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 459      IndexMap index_map,
 460      Compare compare, Combine combine, DistInf inf, DistZero zero,
 461      DijkstraVisitor vis, ColorMap color)
 462   {
 463     typedef typename property_traits<ColorMap>::value_type ColorValue;
 464     typedef color_traits<ColorValue> Color;
 465     typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
 466     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
 467       vis.initialize_vertex(*ui, g);
 468       put(distance, *ui, inf);
 469       put(predecessor, *ui, *ui);
 470       put(color, *ui, Color::white());
 471     }
 472     for (SourceInputIter it = s_begin; it != s_end; ++it) {
 473       put(distance, *it, zero);
 474     }
 475
 476     dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance,
 477                             weight, index_map, compare, combine, zero, vis,
 478                             color);
 479   }
 480
 481   // Initialize distances and call breadth first search
 482   template <class VertexListGraph, class DijkstraVisitor,
 483             class PredecessorMap, class DistanceMap,
 484             class WeightMap, class IndexMap, class Compare, class Combine,
 485             class DistInf, class DistZero, class ColorMap>
 486   inline void
 487   dijkstra_shortest_paths
 488     (const VertexListGraph& g,
 489      typename graph_traits<VertexListGraph>::vertex_descriptor s,
 490      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 491      IndexMap index_map,
 492      Compare compare, Combine combine, DistInf inf, DistZero zero,
 493      DijkstraVisitor vis, ColorMap color)
 494   {
 495     dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
 496                             index_map, compare, combine, inf, zero,
 497                             vis, color);
 498   }
 499
 500   // Initialize distances and call breadth first search
 501   template <class VertexListGraph, class SourceInputIter,
 502             class DijkstraVisitor,
 503             class PredecessorMap, class DistanceMap,
 504             class WeightMap, class IndexMap, class Compare, class Combine,
 505             class DistInf, class DistZero>
 506   inline void
 507   dijkstra_shortest_paths
 508     (const VertexListGraph& g,
 509      SourceInputIter s_begin, SourceInputIter s_end,
 510      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 511      IndexMap index_map,
 512      Compare compare, Combine combine, DistInf inf, DistZero zero,
 513      DijkstraVisitor vis)
 514   {
 515     dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance,
 516                             weight, index_map,
 517                             compare, combine, inf, zero, vis,
 518                             no_named_parameters());
 519   }
 520
 521   // Initialize distances and call breadth first search
 522   template <class VertexListGraph, class DijkstraVisitor,
 523             class PredecessorMap, class DistanceMap,
 524             class WeightMap, class IndexMap, class Compare, class Combine,
 525             class DistInf, class DistZero>
 526   inline void
 527   dijkstra_shortest_paths
 528     (const VertexListGraph& g,
 529      typename graph_traits<VertexListGraph>::vertex_descriptor s,
 530      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 531      IndexMap index_map,
 532      Compare compare, Combine combine, DistInf inf, DistZero zero,
 533      DijkstraVisitor vis)
 534   {
 535     dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance,
 536                             weight, index_map,
 537                             compare, combine, inf, zero, vis);
 538   }
 539
 540   namespace detail {
 541
 542     // Handle defaults for PredecessorMap and
 543     // Distance Compare, Combine, Inf and Zero
 544     template <class VertexListGraph, class DistanceMap, class WeightMap,
 545               class IndexMap, class Params>
 546     inline void
 547     dijkstra_dispatch2
 548       (const VertexListGraph& g,
 549        typename graph_traits<VertexListGraph>::vertex_descriptor s,
 550        DistanceMap distance, WeightMap weight, IndexMap index_map,
 551        const Params& params)
 552     {
 553       // Default for predecessor map
 554       dummy_property_map p_map;
 555
 556       typedef typename property_traits<DistanceMap>::value_type D;
 557       D inf = choose_param(get_param(params, distance_inf_t()),
 558                            (std::numeric_limits<D>::max)());
 559
 560       dijkstra_shortest_paths
 561         (g, s,
 562          choose_param(get_param(params, vertex_predecessor), p_map),
 563          distance, weight, index_map,
 564          choose_param(get_param(params, distance_compare_t()),
 565                       std::less<D>()),
 566          choose_param(get_param(params, distance_combine_t()),
 567                       closed_plus<D>(inf)),
 568          inf,
 569          choose_param(get_param(params, distance_zero_t()),
 570                       D()),
 571          choose_param(get_param(params, graph_visitor),
 572                       make_dijkstra_visitor(null_visitor())),
 573          params);
 574     }
 575
 576     template <class VertexListGraph, class DistanceMap, class WeightMap,
 577               class IndexMap, class Params>
 578     inline void
 579     dijkstra_dispatch1
 580       (const VertexListGraph& g,
 581        typename graph_traits<VertexListGraph>::vertex_descriptor s,
 582        DistanceMap distance, WeightMap weight, IndexMap index_map,
 583        const Params& params)
 584     {
 585       // Default for distance map
 586       typedef typename property_traits<WeightMap>::value_type D;
 587       typename std::vector<D>::size_type
 588         n = is_default_param(distance) ? num_vertices(g) : 1;
 589       std::vector<D> distance_map(n);
 590
 591       detail::dijkstra_dispatch2
 592         (g, s, choose_param(distance, make_iterator_property_map
 593                             (distance_map.begin(), index_map,
 594                              distance_map[0])),
 595          weight, index_map, params);
 596     }
 597   } // namespace detail
 598
 599   // Named Parameter Variant
 600   template <class VertexListGraph, class Param, class Tag, class Rest>
 601   inline void
 602   dijkstra_shortest_paths
 603     (const VertexListGraph& g,
 604      typename graph_traits<VertexListGraph>::vertex_descriptor s,
 605      const bgl_named_params<Param,Tag,Rest>& params)
 606   {
 607     // Default for edge weight and vertex index map is to ask for them
 608     // from the graph.  Default for the visitor is null_visitor.
 609     detail::dijkstra_dispatch1
 610       (g, s,
 611        get_param(params, vertex_distance),
 612        choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
 613        choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
 614        params);
 615   }
 616
 617 } // namespace boost
 618
 619 #ifdef BOOST_GRAPH_USE_MPI
 620 #  include <boost/graph/distributed/dijkstra_shortest_paths.hpp>
 621 #endif
 622
 623 #endif // BOOST_GRAPH_DIJKSTRA_HPP