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

Question

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

谢谢！

Answer 1

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

Answer 2

是，不要breadth_first_search（）从u开始。

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 3

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