Boost dijkstra shortest_path: ¿cómo se puede obtener el camino más corto y no solo la distancia?

Question

Necesito usar la biblioteca de Boost para obtener la ruta más corta de un punto a otro. Revisé el código de ejemplo y es decentemente fácil de seguir. Sin embargo, el ejemplo solo muestra cómo obtener las distancias generales. Estoy tratando de averiguar cómo iterar sobre el mapa predecesor para realmente obtener la ruta más corta y no puedo entenderlo. He leído estas dos preguntas sobre el tema:

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

Sin embargo, en los dos ejemplos proporcionados, no parece el typedef IndexMap para trabajar con el compilador de Visual Studio y, francamente , Los typedefs de Boost son un poco confusos para mí y estoy teniendo algunos problemas para descifrar todo esto. Basado en el código de ejemplo de Boost aquí, ¿alguien podría decirme cómo puedo obtener el camino de salida? Le estaría muy agradecido.

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

Answer 1

Si lo que desea es obtener la ruta del mapa predecesor puede hacerlo de esta manera.

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

Esto es llonesmiz's code ligeramente modificada para mostrar los segmentos intermedios ir de A a los otros nodos, junto con las distancias de segmento:

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] 

CÓDIGO

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