| //======================================================================= |
| // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, |
| // |
| // 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 <iostream> |
| #include <boost/graph/edge_list.hpp> |
| #include <boost/graph/bellman_ford_shortest_paths.hpp> |
| |
| int |
| main() |
| { |
| using namespace boost; |
| // ID numbers for the routers (vertices). |
| enum |
| { A, B, C, D, E, F, G, H, n_vertices }; |
| const int n_edges = 11; |
| typedef std::pair < int, int >Edge; |
| |
| // The list of connections between routers stored in an array. |
| Edge edges[] = { |
| Edge(A, B), Edge(A, C), |
| Edge(B, D), Edge(B, E), Edge(C, E), Edge(C, F), Edge(D, H), |
| Edge(D, E), Edge(E, H), Edge(F, G), Edge(G, H) |
| }; |
| |
| // Specify the graph type and declare a graph object |
| typedef edge_list < Edge*, Edge, std::ptrdiff_t, std::random_access_iterator_tag> Graph; |
| Graph g(edges, edges + n_edges); |
| |
| // The transmission delay values for each edge. |
| float delay[] = |
| {5.0, 1.0, 1.3, 3.0, 10.0, 2.0, 6.3, 0.4, 1.3, 1.2, 0.5}; |
| |
| // Declare some storage for some "external" vertex properties. |
| char name[] = "ABCDEFGH"; |
| int parent[n_vertices]; |
| for (int i = 0; i < n_vertices; ++i) |
| parent[i] = i; |
| float distance[n_vertices]; |
| std::fill(distance, distance + n_vertices, (std::numeric_limits < float >::max)()); |
| // Specify A as the source vertex |
| distance[A] = 0; |
| |
| bool r = bellman_ford_shortest_paths(g, int (n_vertices), |
| weight_map(make_iterator_property_map |
| (&delay[0], |
| get(edge_index, g), |
| delay[0])). |
| distance_map(&distance[0]). |
| predecessor_map(&parent[0])); |
| |
| if (r) |
| for (int i = 0; i < n_vertices; ++i) |
| std::cout << name[i] << ": " << distance[i] |
| << " " << name[parent[i]] << std::endl; |
| else |
| std::cout << "negative cycle" << std::endl; |
| |
| return EXIT_SUCCESS; |
| } |