Boost dijkstra shortest_path - comment obtenir le chemin le plus court et pas seulement la distance?

Question

J'ai besoin d'utiliser la bibliothèque Boost pour obtenir le chemin le plus court d'un point à un autre. J'ai examiné l'exemple de code et il est décemment facile à suivre. Cependant, l'exemple montre seulement comment obtenir les distances globales. J'essaie de comprendre comment itérer sur la carte prédécesseur pour obtenir effectivement le plus court chemin et je ne peux pas sembler comprendre. J'ai lu ces deux questions sur le sujet:

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

Mais dans les deux exemples fournis, le typedef indexmap ne semble pas fonctionner avec le compilateur Visual Studio et, franchement , Boost typedefs sont un peu confus pour moi et j'ai du mal à comprendre tout cela. Basé sur le code d'exemple Boost ici, quelqu'un pourrait-il me dire comment je peux juste en sortir le chemin? Je serais très reconnaissant.

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

Answer 1

Si vous voulez juste pour obtenir le chemin de la carte prédécesseur, vous pouvez le faire comme ça.

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

Ceci est llonesmiz's code légèrement modifié pour afficher les segments intermédiaires allant de A vers les autres noeuds ainsi que les distances de segments:

SORTIE

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