Re: [Boost-users] boost dijkstra : retrieve the whole path

On Wed, 5 Sep 2012, Viviane Parent wrote:

Hello people

I'm stubbling on a very stupid problem I think, but I can't find any hint about it.

I'm using the boost algorithm dijkstra_shortest_path and I simply want to know how to retrieve all the steps the algo goes through for the shortest path found. To illustrate : I'm glad to know that to go from A to Z, the minimal cost is 26, but I would like also to know that this path goes from A to B then from B to C etc.

I used the example http://www.boost.org/doc/libs/1_51 [...] ample.cpp So I ended up with dijkstra_shortest_paths(g, s, &p[0], &d[0], weightmap, indexmap, std::less<int>(), closed_plus<int>(), (std::numeric_limits<int>::max)(), 0,default_dijkstra_visitor()); (I use Visual) Is the info I need somewhere in the visitor, or something ?

There are basically two ways to do it: 1. Walk backwards through the predecessor map: vertex_descriptor v = <whatever>; vector path; do { path.push_back(v); v = get(pred, v); } while (v != s); std::reverse(path.begin(), path.end()); 2. Use predecessor_recorder or edge_predecessor_recorder as a visitor, then use code similar to #1 to find the path for a given vertex. Look at libs/graph/example/bfs.cpp for an example of using the visitor in a BFS context. -- Jeremiah Willcock