graph-theory - 使用 Floyd-Warshall 检测正循环

Question

我见过有人说可以（轻松地）修改 Floyd-Warshall 以检测周期。注意：我假设图表没有负循环。我想知道如何修改算法？为什么它是正确的？另外，你可以让它检测到哪些周期？最短，最长，长度为 k？——你需要对算法进行哪些调整？

我读了这个问题，这让我开始思考这个问题： Find cycle of shortest length in adirected graph with positive weights

对于上面的链接，我不明白为什么要制作 adj 的对角线。matrix = INFINITY 为我们提供了通过 (i,i) 的最短长度的循环。

最后，这个网站：http ://en.algoritmy.net/article/45708/Floyd-Warshall-algorithm 说：

 Floyd-Warshall algorithm can be easily modified to detect cycles. 
 If we fill negative infinity value at the diagonal of the matrix and run the 
 algorithm, then the matrix of predecessors will contain also all cycles in the graph 
 (the diagonal will not contain only zeros, if there is a cycle in the graph).

所以我认为我不明白这一点，因为这似乎是错误的，因为如果记忆对我有用，则无法在多时间内完成检测所有周期。我是否误解了所说的内容？（另外，不太确定前辈矩阵是什么意思。）

Answer 1

我相信前辈矩阵是计算任何顶点到任何其他顶点的距离的最终结果，F_ij=从节点 i 到节点 j 的最短路径长度，如果没有路径，则为 0。如果邻接矩阵的对角线设置为无穷大，它有效地禁止了自循环，因此 F_ii 可以为非零的唯一方法是如果存在从节点 i 到其自身的路径通过至少一个其他节点，即循环。一般来说，任何寻路算法都可以转化为寻环算法。取你想要找到一个循环的节点，比如 v，并将它分成两个节点 v_out 和 v_in，v-out 只有 v 之外的边，v_in 只有 v 中的边。现在使用算法找到从 v_out 到 v_in 的路径，如果 v_out 和 v_in 合并回 v，这将成为一个循环。