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

On Thu, 6 Sep 2012, Viviane Parent wrote:

2012/9/5 Jeremiah Willcock 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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Thanks for your answer

I sorry because I'm a beginner with boost. What you call the predecessor_map, I don't think I have such thing.

The part of my code looks like :

std::vector p(num_vertices(g));   std::vector<int> d(num_vertices(g));   vertex_descriptor s = vertex(i, g);

  boost::default_dijkstra_visitor visitor=boost::default_dijkstra_visitor() ;   // VC++ has trouble with the named parameters mechanism   boost::property_map::type indexmap = get(boost::vertex_index, g);   dijkstra_shortest_paths(g, s, &p[0], &d[0], weightmap, indexmap,                           std::less<int>(), boost::closed_plus<int>(),                           (std::numeric_limits<int>::max)(), 0,                           visitor);

At first, I assumed your "pred" is my "p", but apparently, it's not, or I'm missing something (it doesn't compile, I've got errors in some boost's .h)

It should be, but using &p[0] as a property map might break for some compilers. You might want to try boost::make_iterator_property_map(p.begin(), indexmap) instead. -- Jeremiah Willcock