Boost dijkstra shortest_path - làm thế nào bạn có thể có được con đường ngắn nhất và không chỉ là khoảng cách?

Question

Tôi cần sử dụng thư viện Tăng để có đường đi ngắn nhất từ ​​điểm này đến điểm khác. Tôi đã xem xét mã ví dụ và nó rất dễ làm theo. Tuy nhiên, ví dụ chỉ cho thấy làm thế nào để có được khoảng cách tổng thể. Tôi đang cố gắng tìm hiểu cách lặp lại bản đồ người tiền nhiệm để thực sự nhận được con đường ngắn nhất và tôi dường như không thể tìm ra nó. Tôi đã đọc hai câu hỏi về chủ đề này:

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

Nhưng trong cả hai ví dụ được cung cấp, typedef IndexMap dường như không làm việc với các trình biên dịch Visual Studio, và thẳng thắn , Boost typedefs là một chút bối rối với tôi và tôi đang gặp một số khó khăn trong việc tìm ra tất cả điều này. Dựa trên mã ví dụ Boost ở đây, bất cứ ai có thể cho tôi biết làm thế nào tôi chỉ có thể có được con đường ra khỏi nó? Tôi sẽ rất biết ơn.

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

Answer 1

Nếu bạn chỉ muốn để có được những con đường từ bản đồ người tiền nhiệm của bạn có thể làm điều đó như thế này.

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

Đây là llonesmiz's code chút thay đổi để hiển thị các phân đoạn trung gian đi từ A đến các nút khác cùng với khoảng cách đoạn:

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] 

MÃ

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