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

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_51http://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-**usershttp://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) I'll look at the BFS solution while waiting for new answer Thanks ! V