Zwiększenie dijkstra shortest_path - jak uzyskać najkrótszą ścieżkę, a nie tylko odległość?

Question

Potrzebuję użyć biblioteki Boost, aby uzyskać najkrótszą ścieżkę z jednego punktu do drugiego. Przejrzałem przykładowy kod i przyzwoicie łatwo go śledzić. Jednak przykład pokazuje tylko, jak uzyskać ogólne odległości. Próbuję dowiedzieć się, jak iterować na poprzedniej mapie, aby faktycznie uzyskać najkrótszą ścieżkę i nie mogę tego rozgryźć. Czytałem te dwa pytania na temat:

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

Ale w obu przykładach przedłożone, typedef IndexMap nie wydaje się do pracy z kompilatorem Visual Studio i, szczerze mówiąc , Zwiększenie typedefs jest dla mnie trochę dezorientujące i mam pewne problemy z ustaleniem tego wszystkiego. W oparciu o kod przykładowy Boost może ktoś mi powiedzieć, jak mogę po prostu uzyskać ścieżkę z niego? Byłbym bardzo wdzięczny.

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

Answer 1

Jeśli tylko chcesz uzyskać ścieżkę z mapy poprzednika można to zrobić w ten sposób.

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

to llonesmiz's code nieznacznie zmodyfikowany, aby wyświetlać segmentów pośrednich począwszy od A do innych węzłów oraz odległości segmentu:

WYJŚCIE

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] 

KOD

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