1 | //======================================================================= |
2 | // Copyright 2002 Indiana University. |
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 | /* Expected Output |
11 | 0 1 2 3 4 5 6 7 8 9 |
12 | 0 0 99 111 123 103 107 125 105 111 123 |
13 | 1 99 0 12 24 4 8 26 6 12 24 |
14 | 2 111 12 0 12 16 20 24 18 24 26 |
15 | 3 123 24 12 0 28 30 12 30 26 14 |
16 | 4 103 4 16 28 0 4 22 2 8 20 |
17 | 5 107 8 20 30 4 0 18 6 4 16 |
18 | 6 125 26 24 12 22 18 0 24 14 2 |
19 | 7 105 6 18 30 2 6 24 0 10 22 |
20 | 8 111 12 24 26 8 4 14 10 0 12 |
21 | 9 123 24 26 14 20 16 2 22 12 0 |
22 | */ |
23 | |
24 | #include <boost/config.hpp> |
25 | #include <fstream> |
26 | #include <iostream> |
27 | #include <vector> |
28 | #include <iomanip> |
29 | #include <boost/property_map/property_map.hpp> |
30 | #include <boost/graph/adjacency_list.hpp> |
31 | #include <boost/graph/graphviz.hpp> |
32 | #include <boost/graph/johnson_all_pairs_shortest.hpp> |
33 | |
34 | int main() |
35 | { |
36 | using namespace boost; |
37 | typedef adjacency_list< vecS, vecS, undirectedS, no_property, |
38 | property< edge_weight_t, int, property< edge_weight2_t, int > > > |
39 | Graph; |
40 | const int V = 10; |
41 | typedef std::pair< int, int > Edge; |
42 | Edge edge_array[] = { Edge(0, 1), Edge(1, 2), Edge(2, 3), Edge(1, 4), |
43 | Edge(2, 5), Edge(3, 6), Edge(4, 5), Edge(5, 6), Edge(4, 7), Edge(5, 8), |
44 | Edge(6, 9), Edge(7, 8), Edge(8, 9) }; |
45 | |
46 | const std::size_t E = sizeof(edge_array) / sizeof(Edge); |
47 | |
48 | Graph g(edge_array, edge_array + E, V); |
49 | |
50 | property_map< Graph, edge_weight_t >::type w = get(p: edge_weight, g); |
51 | int weights[] = { 99, 12, 12, 4, 99, 12, 4, 99, 2, 4, 2, 99, 12 }; |
52 | int* wp = weights; |
53 | |
54 | graph_traits< Graph >::edge_iterator e, e_end; |
55 | for (boost::tie(t0&: e, t1&: e_end) = edges(g_: g); e != e_end; ++e) |
56 | w[*e] = *wp++; |
57 | |
58 | std::vector< int > d(V, (std::numeric_limits< int >::max)()); |
59 | int D[V][V]; |
60 | johnson_all_pairs_shortest_paths(g, D, params: distance_map(p: &d[0])); |
61 | |
62 | std::cout << std::setw(5) << " " ; |
63 | for (int k = 0; k < 10; ++k) |
64 | std::cout << std::setw(5) << k; |
65 | std::cout << std::endl; |
66 | for (int i = 0; i < 10; ++i) |
67 | { |
68 | std::cout << std::setw(5) << i; |
69 | for (int j = 0; j < 10; ++j) |
70 | { |
71 | std::cout << std::setw(5) << D[i][j]; |
72 | } |
73 | std::cout << std::endl; |
74 | } |
75 | |
76 | return 0; |
77 | } |
78 | |