123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 |
- //=======================================================================
- // 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;
- }
|