Floyd-Warshall算法适用于负循环

Question

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

Answer 1

在具有负循环的图形中没有最短路径,对于每个路径 - 通过再次遍历循环可以找到更短的路径.

如果你指的是最短的简单路径(每个顶点最多可以访问一次) - 除非P = NP,否则它无法完成,而且很可能不是.

假设您有一个有效的最短简单路径算法A.
给定最长路径问题和图形的实例,在其中G=(V,E,w)创建新图形.现在调用上,和你有最短简单的路径-这是最长的路径.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)).