11

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

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

4

2 回答 2

12

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

//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-01T15:36:59.957 回答
3

这是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;
}
于 2013-01-26T12:31:04.970 回答