algorithm - 带循环的 Floyd-Warshall 算法？

Question

我正在实现 Floyd-Warshall 算法，我有一个问题: 如果我的图中有一个循环(我的意思是，从 A 到 A 的成本是 1)，算法应该输出什么，0(因为从任何节点到同一节点的成本是 0)，或者 1 (因为从 A 到 A 有一条成本为 1 的边？

我没有包含任何代码，因为这就是那个问题。

Answer 1

在Wikipedia article在 Floyd-Warhsall 算法中有一段明确讨论了如何处理负长度的循环，如下所示。

A negative cycle is a cycle whose edges sum to a negative value. There is no shortest path between any pair of vertices i, j which form part of a negative cycle, because path-lengths from i to j can be arbitrarily small (negative). For numerically meaningful output, the Floyd–Warshall algorithm assumes that there are no negative cycles. Nevertheless, if there are negative cycles, the Floyd–Warshall algorithm can be used to detect them.

包括细节在内，最终可以利用算法的内部工作原理如下。

Hence, to detect negative cycles using the Floyd–Warshall algorithm, one can inspect the diagonal of the path matrix, and the presence of a negative number indicates that the graph contains at least one negative cycle.