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

Question

我知道在图中存在负的权重循环时没有找到最小距离的方法，那么就没有最小距离的含义。我的问题是，如果我们将Floyd Warshall算法与负重量周期的图形一起填充会发生什么？它会无限期运行或终止（可能是错误的答案）在O（n ）？

Answer 1

正如你可能找到的Wikipedia
Floyd-Warshall算法没有条件是基于当前的权重或最大权重。
算法只是通过所有的顶点对并计算距离。 所以答案是否定的，它不会无限期地运行。
绝对算法会返回错误的答案（对于消极循环中的顶点，您将有负距离）。例如，从顶点到它自身的距离是负的。

此外，该算法也可用于负循环检测。