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
39namespace 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(e: 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(vis: 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
624

source code of boost/boost/graph/dijkstra_shortest_paths.hpp