Boost Dijkstra Shortest Path Example utilising backtracking from target

18 Aug 2012 . category: . Comments

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.

Stuart James …

Assistant Professor in Visual Computing at Durham University. Stuart's research focus is on Visual Reasoning to understand the layout of visual content from Iconography (e.g. Sketches) to 3D Scene understanding and their implications on methods of interaction. He is currently a co-I on the RePAIR EU FET, DCitizens EU Twinning, and BoSS EU Lighthouse. He was a co-I on the MEMEX RIA EU H2020 project coordinated at IIT for increasing social inclusion with Cultural Heritage. Stuart has previously held a Researcher & PostDoc positions at IIT as well as PostDocs at University College London (UCL), and the University of Surrey. Also, at the University of Surrey, Stuart was awarded his PhD on visual information retrieval for sketches. Stuart holds an External Scientist at IIT, Honorary roles UCL and UCL Digital Humanities, and an international collaborator of ITI/LARSyS. He also regularly organises Vision for Art (VISART) workshop and Humanities-orientated tutorials and was Program Chair at British Machine Conference (BMVC) 2021.