2012/9/5 Jeremiah Willcock <jewillco@osl.iu.edu>
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@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<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