Boost/BGL/DijkstraDirected

From ProgrammingExamples
< Boost‎ | BGL
Revision as of 07:52, 16 November 2011 by Daviddoria (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

DijkstraDirected.cpp

#include <boost/config.hpp>
#include <iostream>
#include <fstream>
 
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>
 
int main(int, char *[])
{
  typedef boost::property<boost::edge_weight_t, float> EdgeWeightProperty;
 
  typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,
    boost::no_property, EdgeWeightProperty > Graph;
 
  typedef boost::graph_traits < Graph >::vertex_descriptor vertex_descriptor;
  typedef boost::graph_traits < Graph >::edge_descriptor edge_descriptor;
  typedef std::pair<int, int> Edge;
 
  // Create a graph
  Graph g;
 
  Graph::vertex_descriptor v0 = boost::add_vertex(g);
  Graph::vertex_descriptor v1 = boost::add_vertex(g);
  Graph::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(v1, v2, weight1, g);
 
  EdgeWeightProperty weight2 = 2;
  boost::add_edge(v2, v0, weight2, g);
 
  // At this point the graph is
  /*   v0
       .
   5  / \ 2
     /___\
    v1 3 v2
  */
 
  // Create things for Dijkstra
  std::vector<vertex_descriptor> parents(boost::num_vertices(g)); // To store parents
  std::vector<int> distances(boost::num_vertices(g)); // To store distances
 
  // Compute shortest paths from v0 to all vertices, and store the output in parents and distances
  boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(&parents[0]).distance_map(&distances[0]));
 
  // Output results
  std::cout << "distances and parents:" << std::endl;
  boost::graph_traits < Graph >::vertex_iterator vertexIterator, vend;
  for (boost::tie(vertexIterator, vend) = boost::vertices(g); vertexIterator != vend; ++vertexIterator) 
  {
    std::cout << "distance(" << *vertexIterator << ") = " << distances[*vertexIterator] << ", ";
    std::cout << "parent(" << *vertexIterator << ") = " << parents[*vertexIterator] << std::endl;
  }
  std::cout << std::endl;
 
  /*
  The output is:
  distance(0) = 0, parent(0) = 0
  distance(1) = 5, parent(1) = 0
  distance(2) = 8, parent(2) = 1
 
  which means:
  the distance from v0 to v0 is 0
  the distance from v0 to v1 is 5
  the distance from v0 to v2 is 8
  */
  return EXIT_SUCCESS;
}

CMakeLists.txt

cmake_minimum_required(VERSION 2.6)
 
Project(DijkstraDirected)
 
set(Boost_USE_MULTITHREADED ON)
FIND_PACKAGE(Boost 1.38 COMPONENTS program_options required)
 
INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS})
 
ADD_EXECUTABLE(DijkstraDirected DijkstraDirected.cpp)