Boost/BGL/DijkstraComputePath

The Dijkstra algorithm in Boost computes the shortest path from a specified vertex to ALL other vertices in the graph. Many times we are interested in the path to one specific vertex. The custom function GetShortestPath follows the 'parents' in the data returned by the Dijkstra algorithm to get the path of interest.

DijkstraComputePath.cpp

#include <boost/config.hpp>
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/properties.hpp>
 
#include <boost/property_map/property_map.hpp>
 
#include <iostream>
#include <utility>
#include <vector>
 
int main(int, char *[])
{
  typedef float Weight;
  typedef boost::property<boost::edge_weight_t, Weight> WeightProperty;
  typedef boost::property<boost::vertex_name_t, std::string> NameProperty;
 
  typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,
    NameProperty, WeightProperty > Graph;
 
  typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
 
  typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
  typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;
 
  typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
  typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap;
 
 
  // Create a graph
  Graph g;
 
  // Add named vertices
  Vertex v0 = boost::add_vertex(std::string("v0"), g);
  Vertex v1 = boost::add_vertex(std::string("v1"), g);
  Vertex v2 = boost::add_vertex(std::string("v2"), g);
  Vertex v3 = boost::add_vertex(std::string("v3"), g);
 
  // Add weighted edges
  Weight weight0 = 5;
  Weight weight1 = 3;
  Weight weight2 = 2;
  Weight weight3 = 4;
 
  boost::add_edge(v0, v1, weight0, g);
  boost::add_edge(v1, v3, weight1, g);
  boost::add_edge(v0, v2, weight2, g);
  boost::add_edge(v2, v3, weight3, g);
 
  // At this point the graph is
  /*    v0
         .
        / \ 2
       /   \
      /     . v2
    5/       \
    /         \ 4
   /           \
  v1----------- v3
      3
  */
 
  // Create things for Dijkstra
  std::vector<Vertex> predecessors(boost::num_vertices(g)); // To store parents
  std::vector<Weight> distances(boost::num_vertices(g)); // To store distances
 
  IndexMap indexMap = boost::get(boost::vertex_index, g);
  PredecessorMap predecessorMap(&predecessors[0], indexMap);
  DistanceMap distanceMap(&distances[0], indexMap);
 
  // Compute shortest paths from v0 to all vertices, and store the output in predecessors and distances
  // boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(predecessorMap).distance_map(distanceMap));
  // This is exactly the same as the above line - it is the idea of "named parameters" - you can pass the
  // prdecessor map and the distance map in any order.
  boost::dijkstra_shortest_paths(g, v0, boost::distance_map(distanceMap).predecessor_map(predecessorMap));
 
  // Output results
  std::cout << "distances and parents:" << std::endl;
  NameMap nameMap = boost::get(boost::vertex_name, g);
 
  BGL_FORALL_VERTICES(v, g, Graph)
  {
    std::cout << "distance(" << nameMap[v0] << ", " << nameMap[v] << ") = " << distanceMap[v] << ", ";
    std::cout << "predecessor(" << nameMap[v] << ") = " << nameMap[predecessorMap[v]] << std::endl;
  }
 
  // Extract a shortest path
  std::cout << std::endl;
 
  typedef std::vector<Graph::edge_descriptor> PathType;
 
  PathType path;
 
  Vertex v = v3; // We want to start at the destination and work our way back to the source
  for(Vertex u = predecessorMap[v]; // Start by setting 'u' to the destintaion node's predecessor
      u != v; // Keep tracking the path until we get to the source
      v = u, u = predecessorMap[v]) // Set the current vertex to the current predecessor, and the predecessor to one level up
  {
    std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(u, v, g);
    Graph::edge_descriptor edge = edgePair.first;
 
    path.push_back( edge );
  }
 
  // Write shortest path
  std::cout << "Shortest path from v0 to v3:" << std::endl;
  float totalDistance = 0;
  for(PathType::reverse_iterator pathIterator = path.rbegin(); pathIterator != path.rend(); ++pathIterator)
  {
    std::cout << nameMap[boost::source(*pathIterator, g)] << " -> " << nameMap[boost::target(*pathIterator, g)]
              << " = " << boost::get( boost::edge_weight, g, *pathIterator ) << std::endl;
 
  }
 
  std::cout << std::endl;
 
  std::cout << "Distance: " << distanceMap[v3] << std::endl;
 
  return EXIT_SUCCESS;
}
 
/*
 * Output:
distances and parents:
distance(v0, v0) = 0, predecessor(v0) = v0
distance(v0, v1) = 5, predecessor(v1) = v0
distance(v0, v2) = 2, predecessor(v2) = v0
distance(v0, v3) = 6, predecessor(v3) = v2
 
Shortest path from v0 to v3:
v0 -> v2 = 2
v2 -> v3 = 4
 
Total distance: 6
 
*/

CMakeLists.txt

cmake_minimum_required(VERSION 2.6)
 
Project(DijkstraComputePath)
 
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(DijkstraComputePath DijkstraComputePath.cpp)