如何修改Floyd-Warshall算法，以找到保持O（V^3）时间复杂性的有向图的任何负代价循环的最短路径？
在具有负循环的图中没有最短路径，对于每条路径，可以通过再次遍历循环找到一条较短的路径。
如果您指的是最短简单路径（每个顶点最多可以访问一次）-它不能完成，除非p=NP，而且很可能不是。
假设您有一个有效的最短简单路径算法A。
给定最长路径问题的一个实例和一个图G=(V,E,w)，创建一个新的图G'=(V,E,w')，其中w'(u,v) = -1*w(u,v)。现在在G'上调用A，得到G'上最短的简单路径，这是G上最长的路径。
然而，由于最长路径是NP难的-这样的解决方案是不可能的，除非p=NP。
tl；dr:
- 在具有负循环的图中，不存在最短路径
- 在
O(V^3)时间内具有负循环的图中找不到最短的简单路径（除非P=NP，即使这样也不一定是O（V^3））