使用Boost的图breadth_first_search()在未加权、无向图中查找路径

Question

我使用的是 adjacency_list 图，具有无向和未加权的边。 我需要找到顶点 u 和顶点 v 之间的最短路径。 我应该从 u 开始使用 breadth_first_search() 吗？ 当到达v时，如何获取路径，如何停止搜索？

谢谢！

Answer 1

是的，从 u 开始执行 breadth_first_search() 。

FOR every vertex i meet
  IF i==v: BREAK
  record predecessor of i as i.p

要找到最短路径，请从 v 开始：

PRINT_PATH(u, v)
  IF v==u
    print u
  ELSEIF v.p==NIL
    print 'no path from u to v exists'
  ELSE PRINT_PATH(u, v.p)
    print v

Answer 2

您应该使用最短路径算法之一， Dijkstra Shortest Path 是最合适的，因为您需要找到两个顶点之间的路径。 有一个示例在 boost 发行版中的使用。 有多种选项可用于从该函数获取输出：通过提供距离属性映射或构建前趋映射或编写自定义访问者。

Answer 3

您需要使用最小生成树：搜索算法。 这是一个非常简单直接的贪心算法。