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://listarchives.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