1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
10 #include <boost/graph/dag_shortest_paths.hpp>
11 #include <boost/graph/adjacency_list.hpp>
15 // Example from Introduction to Algorithms by Cormen, et all p.537.
27 using namespace boost
;
28 typedef adjacency_list
< vecS
, vecS
, directedS
,
29 property
< vertex_distance_t
, int >, property
< edge_weight_t
, int > >
41 char name
[] = "rstuvx";
49 add_edge(u
, v
, -1, g
);
51 add_edge(v
, x
, -2, g
);
53 property_map
< graph_t
, vertex_distance_t
>::type d_map
54 = get(vertex_distance
, g
);
56 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
57 // VC++ has trouble with the named-parameter mechanism, so
58 // we make a direct call to the underlying implementation function.
59 std::vector
< default_color_type
> color(num_vertices(g
));
60 std::vector
< std::size_t > pred(num_vertices(g
));
61 default_dijkstra_visitor vis
;
62 std::less
< int > compare
;
63 closed_plus
< int > combine
;
64 property_map
< graph_t
, edge_weight_t
>::type w_map
= get(edge_weight
, g
);
65 dag_shortest_paths(g
, s
, d_map
, w_map
, &color
[0], &pred
[0], vis
, compare
,
66 combine
, (std::numeric_limits
< int >::max
)(), 0);
68 dag_shortest_paths(g
, s
, distance_map(d_map
));
71 graph_traits
< graph_t
>::vertex_iterator vi
, vi_end
;
72 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
73 if (d_map
[*vi
] == (std::numeric_limits
< int >::max
)())
74 std::cout
<< name
[*vi
] << ": inifinity\n";
76 std::cout
<< name
[*vi
] << ": " << d_map
[*vi
] << '\n';