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-06 09:26:26

On Thu, 6 Sep 2012, Viviane Parent wrote:

> 
> 
> 2012/9/5 Jeremiah Willcock <jewillco_at_[hidden]>
>       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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> 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<vertex_descriptor> 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<graph_t, boost::vertex_index_t>::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