Floyd Warshall 算法在负权重循环上的时间复杂度

Question

我知道当图中有负权重环时，没有找到最小距离的方法，也就没有最小距离的意义了。我的问题是，如果我们向 Floyd Warshall 算法提供具有负权重循环的图，会发生什么情况？它会 运行 无限期地终止还是在 O(n³) 中终止（可能答案错误）？

Answer 1

您可能会在 Wikipedia
上找到 Floyd-Warshall 算法中没有基于当前重量或最大重量的条件。
算法只是遍历所有顶点对并计算距离。 所以答案是否定的，它不会无限期地运行。
并且算法肯定会 return 错误答案（对于负循环中的顶点，您将有负距离）。例如，从顶点到自身的距离将为负数。

另外这个算法也可以用于负循环检测。