[ create a new paste ] login | about

Link: http://codepad.org/7lFgHka9    [ raw code | fork ]

C++, pasted on Jun 7:
#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <map>

#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::adjacency_list<     boost::listS,             // out-edges stored in a std::list
                       boost::vecS,             // vertex set stored here
                       boost::undirectedS,    // bidirectional graph.
                       boost::no_property,              // vertex properties
                       EdgeWeightProperty,       // edge properties
                       boost::no_property,       // graph properties
                       boost::listS              // edge storage
                       > 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
  vertex_descriptor v0 = boost::add_vertex(g);
  vertex_descriptor v1 = boost::add_vertex(g);
  vertex_descriptor v2 = boost::add_vertex(g);
  
  // Add weighted edges
  EdgeWeightProperty weight0 = 5;
  boost::add_edge( v0, v1, weight0, g);
  
  EdgeWeightProperty weight1 = 3;
  boost::add_edge( v0, v2, weight1, g);
  
  EdgeWeightProperty weight2 = 2;
  boost::add_edge( v1, v2, weight2, g);

  // predecessor map with key and value type of vertex_descriptor
  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(" << *vi << ") = " << d[*vi] << ", ";
    std::cout << "parent(" << *vi << ") = " << p[*vi] << std::endl;
  }
  std::cout << std::endl;

  return EXIT_SUCCESS;
}


Create a new paste based on this one


Comments: