Boost dijkstra shortest_path - 你如何获得最短路径而不仅仅是距离？

我需要使用Boost库来获取从一个点到另一个点的最短路径。我查看了示例代码，它很容易遵循。但是，该示例仅显示如何获得总距离。我想弄清楚如何遍历前导映射到得到最短的路径，我似乎无法弄清楚。我读过关于这个问题的两个问题：Boost dijkstra shortest_path - 你如何获得最短路径而不仅仅是距离？

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

但在这两个所提供的例子中，IndexMap的typedef似乎并没有与Visual Studio编译器，坦率地说工作，Boost typedefs对我来说有点令人困惑，而且我在计算所有这些时遇到了一些麻烦。基于这里的Boost示例代码，有谁能告诉我如何才能从中获得路径吗？我会非常感谢。

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

来源

2012-10-01 Darkenor

如果你只是想从前身地图的路径，你可以不喜欢这样。

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

来源

2012-10-01 15:36:59

注 - 我认为你必须添加path.push_back（current）;在你进入最后的path.push_back（start）之前; - 当我使用它时，它会在最后一个之前忘记节点。 – Darkenor

@Darkenor对不起，我相信它现在可以正常工作。 – 2012-10-01 18:41:42

Thx为有用的片段！是否很难修改此代码以显示细分的单独距离？ – kfmfe04

这是llonesmiz's code稍加修改，以显示中间段从A到其他节点与段的距离沿着：

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]

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

来源

2013-01-26 12:31:04 kfmfe04

Boost dijkstra shortest_path - 你如何获得最短路径而不仅仅是距离？

回答

相关问题