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

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