algorithm - 适用于负循环的 Floyd-Warshall 算法

Question

如何修改 Floyd-Warshall 算法以找到保持 O(V^3) 时间复杂度的有向图的任何负成本循环的最短路径？

Answer 1

在具有负循环的图中没有最短路径，对于每条路径 - 通过再遍历循环一次可以找到更短的路径。

如果您指的是最短简单路径（每个顶点最多可以访问一次）-它不能完成，除非P=NP，而且很可能不是。

假设您有一个有效的最短简单路径算法A。
给定最长路径问题的一个实例和一个图，在其中G=(V,E,w)创建一个新图。现在调用on ，你得到了最短的简单路径 on - 这是最长的路径 on 。G'=(V,E,w')w'(u,v) = -1*w(u,v)AG'G'G

然而，由于最长路径是NP-Hard - 除非 P=NP，否则这种解决方案是不可能的。

---

tl;博士：

• 在具有负循环的图中，没有最短路径之类的东西。
• 您无法在具有负周期O(V^3)时间的图中找到最短的简单路径（除非 P = NP，即使那样也不一定是 O(V^3)）。