<分区>
如何修改 Floyd-Warshall 算法以找到保持 O(V^3) 时间复杂度的有向图的任何负成本循环的最短路径？
<分区>
如何修改 Floyd-Warshall 算法以找到保持 O(V^3) 时间复杂度的有向图的任何负成本循环的最短路径？
最佳答案
在负环图中没有最短路径，对于每条路径 - 可以通过再次遍历循环找到更短的路径。
如果您指的是最短简单路径(每个顶点最多可以访问一次)- 它无法完成，除非P=NP ，而且很可能不是。
假设您有一个高效的最短简单路径算法 A。
给定Longest Path Problem的实例和图 G=(V,E,w)，创建一个新图 G'=(V,E,w') 其中 w'(u ,v) = -1*w(u,v)。现在在 G' 上调用 A，您得到了 G' 上的最短简单路径 - 这是 G< 上的最长路径.
但是，由于最长路径是 NP-Hard - 这样的解决方案是不可能的，除非 P=NP。
tl;dr:
O(V^3) 时间内找到具有负循环的图中的最短简单路径(除非 P=NP，即使那样它也不确定为 O(V^3 )).关于algorithm - 适用于负循环的 Floyd-Warshall 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28703794/