提高dijkstra shortest_path-如何获得最短的路径而不仅仅是距离? [英] Boost dijkstra shortest_path - how can you get the shortest path and not just the distance?

问题描述

我需要使用Boost库来获得从一个点到另一个点的最短路径.我查看了示例代码，并且很容易理解.但是，该示例仅显示了如何获得总距离.我试图弄清楚如何遍历前导图以实际上 get 最短的路径，但我似乎无法弄清楚.我已经阅读了有关此问题的两个问题:

I have a need to use the Boost library to get the shortest path from one point to another. I've looked over the example code and it is decently easy to follow. However, the example only shows how to get the overall distances. I'm trying to figure out how to iterate over the predecessor map to actually get the shortest path and I can't seem to figure it out. I've read these two questions on the subject:

在提升图中具有VertexList = ListS的Dijkstra最短路径

Boost :: Dijkstra最短路径，如何从路径迭代器获取顶点索引?

但是在提供的两个示例中，IndexMap typedef似乎不适用于Visual Studio编译器，坦率地说，Boost typedef使我有些困惑，而且在弄清所有这些方面都遇到了一些麻烦.根据此处的Boost示例代码，有谁能告诉我我如何才能摆脱困境?我会非常感激.

But in both of the examples provided, the IndexMap typedef doesn't seem to work with the Visual Studio compiler and, frankly, Boost typedefs are a little confusing to me and I'm having some trouble figuring all of this out. Based on the Boost example code here, could anyone tell me how I can just get the path out of it? I would be very thankful.

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

推荐答案

如果您只想从前任地图中获取路径，则可以这样做.

If you just want to get the path from the predecessor map you can do it like this.

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

这篇关于提高dijkstra shortest_path-如何获得最短的路径而不仅仅是距离?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！