algorithm - 调整 Floyd-Warshall 算法来检测周期

Question

干杯，我正在尝试解决有向图中的最小长度循环问题，并且我遇到了一个解决方案，该解决方案建议我应该调整 Floyd-Warshall 算法来解决该问题。它指出，我不应该设置 path[i][i] = 0 我应该设置 path[i][i] = INFINITY，但我不太明白为什么会这样!我发现Floyd-Warshall使用的数组的主对角线没有改变，那么它如何帮助我看到循环的路径？我知道算法生成的数组可以帮助我找到一对的最短路径。例如path[i][j] 给出了从 i 到 j 的最短路径，但是，尽管直觉保持不变，但我发现什么也没有改变，我无法得到想要的结果。

我什至尝试使用此网站 here 可视化该过程，我生成了一个图，其中包含许多循环，但是尽管对角线初始化为无穷大，但它并没有改变。谁能解释我缺少什么或者我可以做些什么来解决我的问题？

Answer 1

对于有向图，其想法是您只需更改 path 矩阵，这样就不需要存储从 i 到 的最短路径的长度j, path[i][j] 存储最短非空路径的长度，即它只包含至少有一条边的路径。当然，这只影响从顶点到自身的路径。

所以现在，我们用infinity而不是0来初始化path[i][i]，因为我们当时还没有找到任何非空路径顶点到其自身。

然后，根据边初始化矩阵的其余部分后，我们进行正常的 Floyd-Warshall 迭代:

for k in |V|:
    for j in |V|:
        for i in |V|:
            path[i][j] = min(path[i][j], path[i][k] + path[k][j])

假设有一个简单的循环 1 -> 2 -> 1。然后，当 (i,j,k) == (1,1,2) 时，我们执行 路径[1][1] = min(路径[1][1], 路径[1][2] + 路径[2][1])

这会将 path[1][1] 从无穷大更改为循环长度。

如果您修改了一个实现，但它没有执行此操作，那么该实现可能已优化为完全忽略对角线。