123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 |
- //=======================================================================
- // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
- // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <boost/graph/dag_shortest_paths.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <iostream>
- // Example from Introduction to Algorithms by Cormen, et all p.537.
- // Sample output:
- // r: inifinity
- // s: 0
- // t: 2
- // u: 6
- // v: 5
- // x: 3
- int main()
- {
- using namespace boost;
- typedef adjacency_list<vecS, vecS, directedS,
- property<vertex_distance_t, int>, property<edge_weight_t, int> > graph_t;
- graph_t g(6);
- enum verts { r, s, t, u, v, x };
- char name[] = "rstuvx";
- add_edge(r, s, 5, g);
- add_edge(r, t, 3, g);
- add_edge(s, t, 2, g);
- add_edge(s, u, 6, g);
- add_edge(t, u, 7, g);
- add_edge(t, v, 4, g);
- add_edge(t, x, 2, g);
- add_edge(u, v, -1, g);
- add_edge(u, x, 1, g);
- add_edge(v, x, -2, g);
- property_map<graph_t, vertex_distance_t>::type
- d_map = get(vertex_distance, g);
- #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- // VC++ has trouble with the named-parameter mechanism, so
- // we make a direct call to the underlying implementation function.
- std::vector<default_color_type> color(num_vertices(g));
- std::vector<std::size_t> pred(num_vertices(g));
- default_dijkstra_visitor vis;
- std::less<int> compare;
- closed_plus<int> combine;
- property_map<graph_t, edge_weight_t>::type w_map = get(edge_weight, g);
- dag_shortest_paths(g, s, d_map, w_map, &color[0], &pred[0],
- vis, compare, combine, (std::numeric_limits<int>::max)(), 0);
- #else
- dag_shortest_paths(g, s, distance_map(d_map));
- #endif
- graph_traits<graph_t>::vertex_iterator vi , vi_end;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- if (d_map[*vi] == (std::numeric_limits<int>::max)())
- std::cout << name[*vi] << ": inifinity\n";
- else
- std::cout << name[*vi] << ": " << d_map[*vi] << '\n';
- return 0;
- }
|