提升dijkstra最短路径算法 - 如何获取最短路径而不仅仅是距离？

Question

我需要使用Boost库来获取从一个点到另一个点的最短路径。我查看了示例代码，很容易理解。然而，该示例仅显示如何获取总距离。我正在尝试弄清楚如何迭代前任映射以实际获取最短路径，但似乎无法弄清楚。我阅读了这两个关于此主题的问题：

使用VertexList = ListS在boost图中进行Dijkstra最短路径

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

但是，在提供的这两个示例中，IndexMap typedef似乎与Visual Studio编译器不兼容，而且，Boost typedef对我来说有点混淆，我遇到了一些困难。基于Boost示例代码 http://www.boost.org/doc/libs/1_46_1/libs/graph/example/dijkstra-example.cpp ，有没有人可以告诉我如何只从中获取路径呢？我将非常感激。

- Darkenor

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;

- user1252091

---

注意 - 我认为你需要在最终的path.push_back(start);之前添加path.push_back(current); - 当我使用它时，它总是忘记了倒数第二个节点。 - Darkenor

@Darkenor 对不起，我相信现在它已经正确地工作了。 - user1252091

谢谢你提供这个有用的代码片段！修改这段代码以显示各段的距离会很难吗？ - kfmfe04

非常出色的答案，很多文档似乎忽略了这个难题的部分。谢谢。 - AndyUK

Answer 2

这是 llonesmiz 的代码 稍作修改，以显示从 A 到其它节点的中间路径段及其距离:

输出结果

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]

代码

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

- kfmfe04