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

Subject: Re: [Boost-users] boost dijkstra : retrieve the whole path
From: Viviane Parent (foxadpatres_at_[hidden])
Date: 2012-09-06 03:59:02

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)

I'll look at the BFS solution while waiting for new answer

Thanks !

V