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

Subject: Re: [Boost-users] boost dijkstra : retrieve the whole path
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-09-05 12:50:31

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<vertex_descriptor> 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