1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8 #include <iostream>
9 #include <boost/graph/edge_list.hpp>
10 #include <boost/graph/bellman_ford_shortest_paths.hpp>
11
main()12 int main()
13 {
14 using namespace boost;
15 // ID numbers for the routers (vertices).
16 enum
17 {
18 A,
19 B,
20 C,
21 D,
22 E,
23 F,
24 G,
25 H,
26 n_vertices
27 };
28 const int n_edges = 11;
29 typedef std::pair< int, int > Edge;
30
31 // The list of connections between routers stored in an array.
32 Edge edges[] = { Edge(A, B), Edge(A, C), Edge(B, D), Edge(B, E), Edge(C, E),
33 Edge(C, F), Edge(D, H), Edge(D, E), Edge(E, H), Edge(F, G),
34 Edge(G, H) };
35
36 // Specify the graph type and declare a graph object
37 typedef edge_list< Edge*, Edge, std::ptrdiff_t,
38 std::random_access_iterator_tag >
39 Graph;
40 Graph g(edges, edges + n_edges);
41
42 // The transmission delay values for each edge.
43 float delay[] = { 5.0, 1.0, 1.3, 3.0, 10.0, 2.0, 6.3, 0.4, 1.3, 1.2, 0.5 };
44
45 // Declare some storage for some "external" vertex properties.
46 char name[] = "ABCDEFGH";
47 int parent[n_vertices];
48 for (int i = 0; i < n_vertices; ++i)
49 parent[i] = i;
50 float distance[n_vertices];
51 std::fill(
52 distance, distance + n_vertices, (std::numeric_limits< float >::max)());
53 // Specify A as the source vertex
54 distance[A] = 0;
55
56 bool r = bellman_ford_shortest_paths(g, int(n_vertices),
57 weight_map(
58 make_iterator_property_map(&delay[0], get(edge_index, g), delay[0]))
59 .distance_map(&distance[0])
60 .predecessor_map(&parent[0]));
61
62 if (r)
63 for (int i = 0; i < n_vertices; ++i)
64 std::cout << name[i] << ": " << distance[i] << " "
65 << name[parent[i]] << std::endl;
66 else
67 std::cout << "negative cycle" << std::endl;
68
69 return EXIT_SUCCESS;
70 }
71