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

Question

我需要使用 Boost 库来获取从一点到另一点的最短路径。我查看了示例代码，它非常容易理解。但是，该示例仅显示了如何获取总距离。我试图弄清楚如何迭代前任 map 以实际获得最短路径，但我似乎无法弄清楚。我已经阅读了关于这个主题的这两个问题:

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 typedef 让我有点困惑，我在弄清楚所有这些方面遇到了一些麻烦。基于此处的 Boost 示例代码，谁能告诉我如何才能摆脱困境？我将不胜感激。

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

Answer 1

如果你只是想从前任 map 中获取路径，你可以这样做。

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