Boost dijkstra shortest_path - how can you get the shortest path, not just distance?

Question

I need to use the Boost library to get the shortest path from one point to another. I looked at the sample code, and it is worthy of easy to follow. However, the example only shows how to get the total distances. I am trying to figure out how to iterate over a predecessor card to actually get the shortest path, and I cannot figure it out. I read these two questions on this issue:

The shortest Dijkstra path with VertexList = ListS in the acceleration graph

Boost :: Dijkstra Shortest Path, how to get vertex index from path iterator?

But in both examples presented, typedef IndexMap does not seem to work with the Visual Studio compiler, and to be honest, Boost typedefs are a bit confusing to me, and I am having some problems with this. Based on the Boost example, can someone tell me how can I just get the path out of it? I would be very grateful.

http://www.boost.org/doc/libs/1_46_1/libs/graph/example/dijkstra-example.cpp

Answer 1

If you just want to get the path from the predecessor card, you can do it as follows.

//p[] is the predecessor map obtained through dijkstra //name[] is a vector with the names of the vertices //start and goal are vertex descriptors std::vector< graph_traits< graph_t >::vertex_descriptor > path; graph_traits< graph_t >::vertex_descriptor current=goal; while(current!=start) { path.push_back(current); current=p[current]; } path.push_back(start); //This prints the path reversed use reverse_iterator and rbegin/rend std::vector< graph_traits< graph_t >::vertex_descriptor >::iterator it; for (it=path.begin(); it != path.end(); ++it) { std::cout << name[*it] << " "; } std::cout << std::endl; 

Answer 2

This llonesmiz code has been slightly modified to display intermediate segments going from A to other nodes along with segment distances:

OUTPUT

 A[0] C[1] D[3] E[1] B[1] A[0] C[1] A[0] C[1] D[3] A[0] C[1] D[3] E[1] 

CODE

 // DISPLAY THE PATH TAKEN FROM A TO THE OTHER NODES nodes start = A; for ( int goal=B; goal<=E; ++goal ) { std::vector< graph_traits< graph_t >::vertex_descriptor > path; graph_traits< graph_t >::vertex_descriptor current=goal; while( current!=start ) { path.push_back( current ); current = p[current]; } path.push_back( start ); // rbegin/rend will display from A to the other nodes std::vector< graph_traits< graph_t >::vertex_descriptor >::reverse_iterator rit; int cum=0; for ( rit=path.rbegin(); rit!=path.rend(); ++rit) { std::cout << name[*rit] << "[" << d[*rit]-cum << "] "; cum = d[*rit]; } std::cout << std::endl; }