Difference between revisions of "Boost/BGL/DijkstraComputePath"
From ProgrammingExamples
Daviddoria (Talk | contribs) |
Daviddoria (Talk | contribs) |
||
Line 77: | Line 77: | ||
// Compute shortest paths from v0 to all vertices, and store the output in predecessors and distances | // 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)); | + | // 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. | |
− | // This is | + | boost::dijkstra_shortest_paths(g, v0, boost::distance_map(distanceMap).predecessor_map(predecessorMap)); |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | // | + | |
− | boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(predecessorMap)); | + | |
− | + | ||
// Output results | // Output results |
Revision as of 16:52, 14 June 2011
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)