提升dijkstra shortest_path - 你怎么能得到最短路径而不仅仅是距离？

Question

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

具有VertexList的Dijkstra最短路径=增强图中的ListS

Boost :: Dijkstra Shortest Path,如何从路径迭代器获取顶点索引？

但是在提供的两个示例中,IndexMap typedef似乎不能与Visual Studio编译器一起使用,坦率地说,Boost typedef对我来说有点混乱,我在解决所有这些问题时遇到了一些麻烦.根据这里的Boost示例代码,有人能告诉我如何才能找到它的路径吗？我会非常感激.

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

Answer 1

如果您只想从前一个映射中获取路径,则可以这样做.

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