algorithm - 使用 BFS 查找两个节点之间的所有路径

Question

是否有可能在多项式时间内找到从 s 到 t（s，t 是顶点）的所有可能路径？如果它是什么可能的算法呢？

Answer 1

可以在多项式时间内枚举图中所有可以成为从 s 到 t 的路径的一部分的节点和边。例如，在图中

s --> a --> t
       \
        \--> b

这些节点是 {a}，因为没有从 s 到 t 的路径通过 b。

也可以 在多项式时间内枚举必须在从 s 到 t 的任何路径上的那些节点和边。

只要在多项式时间内不允许循环，您还可以计算从 s 到 t 的路径数；例如，当图形是非循环的，或者当你限制只计算不包含循环的路径时，在多项式时间内。

但是你不能在多项式时间内明确地枚举从 s 到 t 的所有非循环路径，因为它们的数量可能成倍增加。即使在无环图中，例如

   o   o   o         o
  / \ / \ / \       / \
 s   o   o   o ... o   t
  \ / \ / \ /       \ /
   o   o   o         o

假设图形是从左到右的方向；如果其中有 n 个菱形，则它有 2 ^{n条从 s 到 t 的路径。}

找到从 s 到 t 的最长路径是 NP-hard，即没有多项式算法。

计算从 s 到 t 的不相交路径的最大数量也是 NP 难的，也就是说，如果你想枚举从 s 到 t 的一组路径，那么你的集合中的任何两条路径之间都没有公共边。