Boost dijkstra shortest_path - sadece mesafeyi değil, en kısa yolu nasıl elde edersiniz?

Question

En kısa yolu bir noktadan diğerine almak için Destek kütüphanesini kullanmam gerekiyor. Örnek kod üzerinde baktım ve takip etmek kolay. Ancak, örnek yalnızca genel mesafelerin nasıl alınacağını gösterir. Ben bir önceki harita üzerinde yinelemeye çalışıyorum aslında en kısa yol olsun ve bunu anlayamıyorum. Ben konuyla ilgili olarak şu iki soru okudum: Boost:: Dijkstra Shortest Path, how to get vertice index from path iterator?

Fakat örnekler sağlanan her ikisinde de

Dijkstra Shortest Path with VertexList = ListS in boost graph

, IndexMap typedef açıkçası Visual Studio derleyici ve, çalışmak için görünmüyor , Boost typedefs biraz kafa karıştırıcı ve ben tüm bunları anlamaya bazı sorun yaşıyorum. Boost örnek koduna dayanarak, bana yoldan nasıl çıkabileceğimi söyleyen var mı? Çok minnettar olurum. Sadece öncel haritadan yol almak istiyorsanız

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

Answer 1

Eğer böyle yapabilirsiniz.

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

Bu hafif ara parça kademeli mesafeler ile birlikte diğer düğümlere bir gidiş görüntülemek için modifiye llonesmiz's code olup:

ÇIKIŞ

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