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

Question

I have a need to use the Boost library to get the shortest path from one point to another. I've looked over the example code and it is decently easy to follow. However, the example only shows how to get the overall distances. I'm trying to figure out how to iterate over the predecessor map to actually get the shortest path and I can't seem to figure it out. I've read these two questions on the subject:

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

But in both of the examples provided, the IndexMap typedef doesn't seem to work with the Visual Studio compiler and, frankly, Boost typedefs are a little confusing to me and I'm having some trouble figuring all of this out. Based on the Boost example code here, could anyone tell me how I can just get the path out of it? I would be very thankful.

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

score 12 · Accepted Answer · edited Jan 26 '13 at 11:55

12

If you just want to get the path from the predecessor map you can do it like this.

//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;

edited Jan 26 '13 at 11:55

kfmfe04

14,936
14
74
140

answered Oct 01 '12 at 15:36

Note - I think you have to add path.push_back(current); right before you to the final path.push_back(start); - when I used it, it kept forgetting the node before the last one. – Darkenor Oct 01 '12 at 18:18
1

@Darkenor Sorry about that, I believe it now works correctly. – Oct 01 '12 at 18:41
Thx for the useful snippet! Would it be hard to modify this code to display the individual distances for the segments as well? – kfmfe04 Jan 26 '13 at 12:10
Splendid answer, much of the documentation seems to miss this part of the puzzle. Thanks. – AndyUK Nov 04 '15 at 22:41

score 3 · Answer 2 · edited May 23 '17 at 11:46

This is llonesmiz's code slightly modified to display the intermediate segments going from A to the other nodes along with the 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;
}

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

2 Answers2

Linked