Boost dijkstra shortest_path - come puoi ottenere il percorso più breve e non solo la distanza?

Question

Ho bisogno di utilizzare la libreria Boost per ottenere il percorso più breve da un punto a un altro. Ho esaminato il codice di esempio ed è decentemente facile da seguire. Tuttavia, l'esempio mostra solo come ottenere le distanze complessive. Sto cercando di capire come iterare sulla mappa del predecessore in realtà ottenere il il percorso più breve e non riesco a capirlo. Ho letto queste due domande sul tema:

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

Ma in entrambi gli esempi forniti, il typedef IndexMap non sembra funzionare con il compilatore Visual Studio e, francamente I miglioramenti al typedef mi confondono un po 'e sto avendo qualche problema a capire tutto questo. Basato sul codice di esempio di Boost qui, qualcuno potrebbe dirmi come posso ottenere il percorso da esso? Sarei molto grato.

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

Answer 1

Se si desidera solo per ottenere il percorso dalla mappa predecessore si può fare in questo modo.

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

Questo è llonesmiz's code leggermente modificata per visualizzare i segmenti intermedi andare da A a altri nodi insieme alle distanze 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] 

CODICE

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