algorithm - 找到一种使用 O(n 4 ) 时间计算有向图的传递闭包的算法

Question

对于一项作业，我被要求找到一种算法，该算法使用 O(n 4 ) 时间计算有向图的传递闭包。我们已经了解了 floyd warshall 算法，它要好得多，所以有人可以帮我创建一个运行时间为 O(n4) 的算法吗？有这样的算法吗？

我知道这个问题似乎很愚蠢。我真的不明白为什么我们被要求找到更慢的方法来做到这一点。

Answer 1

Floyd Warshall 是 O(n^3)，因为 O(n^3) 是 O(n^4 )，它也是 O(n^4)。
因此，通过设置新图G'=(V,E',w')，其中E' = V x V(团，完整图)并且 w'(u,v) = 1 如果 (u,v) 在 E 中，否则为 INFINITY - 通过使用 Floyd-Warshall 算法，每对 (u,v) 最终的值小于闭包中的无穷大。

---

Theta(n^4) 解:

Q <- E (init) #(Q is a set)
for i from 1 to n:
   for each v in V:
     for each w in V:
        for each u in V:
            if (v,w) is in Q and (w,u) is in E:
               Q <- Q U {(v,u)}  #add (v,u) to Q

复杂度是Theta(n^4)，我们只需要证明它确实找到了传递闭包。

归纳法:

1. 对于从 u 到 v 的长度为 1 的最短路径，它是基本子句，因为 (u,v) 在 E 中。
2. 对于每个 k:
   具有最短路径长度k>1的每对(u,v) - 存在w使得存在一条路径u -> ... -> w，以及一条边 (w,v)。根据归纳假设，在之前的迭代中，我们将 (u,w) 添加到 Q，因此条件会产生 true，我们将添加 (u,v ) 到结果集 Q。

类似证明，如果将某个对(u,v)添加到Q，则有一条路径u->..->w->v，因此它被正确地添加了。

---

第二个Theta(n^4) 解决方案:

设置 G' 如上所述，对于 V 中的每个顶点 v 从 v 运行 Bellman Ford .
BF每次运行Theta(n^3)¹，运行n次是Theta(n^ 4)

---

(1) 技术上它是 O(VE)，但对于非稀疏图，E 是 Theta(V^2)