codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <boost/config.hpp> #include <iostream> #include <fstream> #include <boost/graph/graph_traits.hpp> #include <boost/graph/undirected_graph.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> int main(int, char *[]) { typedef boost::property<boost::edge_weight_t, float> EdgeWeightProperty; typedef boost::undirected_graph<boost::no_property, EdgeWeightProperty > graph_t; typedef boost::graph_traits < graph_t >::vertex_descriptor vertex_descriptor; typedef boost::graph_traits < graph_t >::edge_descriptor edge_descriptor; typedef std::pair<int, int> Edge; // Create a graph graph_t g; // Add vertices graph_t::vertex_descriptor v0 = g.add_vertex(); graph_t::vertex_descriptor v1 = g.add_vertex(); graph_t::vertex_descriptor v2 = g.add_vertex(); // Add weighted edges EdgeWeightProperty weight0 = 5; g.add_edge(v0, v1, weight0); EdgeWeightProperty weight1 = 3; g.add_edge(v1, v2, weight1); EdgeWeightProperty weight2 = 2; g.add_edge(v2, v0, weight2); // Create things for Dijkstra std::vector<vertex_descriptor> p(boost::num_vertices(g)); std::vector<int> d(boost::num_vertices(g)); // Compute shortest paths boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(&p[0]).distance_map(&d[0])); // Output results std::cout << "distances and parents:" << std::endl; boost::graph_traits < graph_t >::vertex_iterator vi, vend; for (boost::tie(vi, vend) = boost::vertices(g); vi != vend; ++vi) { // std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", "; // std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::endl; } std::cout << std::endl; return EXIT_SUCCESS; }
Private
[
?
]
Run code
Submit