Boost Dijkstra Shortest Path Example utilising backtracking from target

Often API documentation can be difficult to follow and your memory might fail for algorithms you learnt in school, so a simple example often explains how to use a function. Well unless you are very familiar with the way Boost Graph library works then you may find the Dijkstra shortest path documentation confusing.

So this is what you get from boost…

1 typedef adjacency_list < listS, vecS, directedS, 2 no_property, property < edge_weight_t, int > > graph_t; 3 typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; 4 typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; 5 typedef std::pair<int, int> Edge; 6 7 const int num_nodes = 5; 8 enum nodes { A, B, C, D, E }; 9 char name[] = "ABCDE"; 10 Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E), 11 Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B) 12 }; 13 int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 }; 14 int num_arcs = sizeof(edge_array) / sizeof(Edge); 15 16 graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); 17 property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g); 18 19 std::vector<vertex_descriptor> p(num_vertices(g)); 20 std::vector<int> d(num_vertices(g)); 21 vertex_descriptor s = vertex(A, g); 22 23 dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));

Taken from http://www.boost.org/doc/libs/1_49_0/libs/graph/example/dijkstra-example.cpp

From this example you are able to get the predecessor map and the distances travelled from a root node to all other nodes. But this doesn’t answer the question of how you get the shortest path from point A to point B. The way to do this is called backtracking and is very easy but not necessarily obvious when you don't know the data structures.

1 // Backtrack from end node, storing distances 2 int target = vertex(B, g); 3 std::vector<int> nodes; 4 std::vector<float> distance; 5 do{ 6 nodes.push_back(target); 7 distances.push_back(d[target]); 8 target = p[target]; 9 }while(target != s);

The vector nodes then contains a list of nodes passed through, that can be reversed easily using std lib functions to find the route from A to B.

Saturday, August 18, 2012 10:51:00 PM Categories: API C++ HowTo
Stuart James