调整Floyd-Warshall算法检测循环

Question

干杯，我正试图解决有向图中最小长度循环的问题，我遇到了一个解决方案，它建议我应该调整Floyd算法来解决这个问题。它说，与其设置path[i][i] = 0，不如设置path[i][i] = INFINITY，但我不太明白为什么会这样！我发现弗洛伊德-沃尔使用的阵列的主对角线没有变化，所以它能帮助我看到循环的路径吗？据我所知，生成的数组的算法帮助我找到最短的路径对。path[i][j]给了我从i到j的最短路径，但是，虽然直觉保持不变，但我看到没有什么变化，我不能取得预期的结果。

我甚至尝试可视化这个过程，使用这个网站这里，我生成了一个包含许多循环的图形，但是虽然对角线是用无穷大来初始化的，但是它不会被改变。有人能解释我错过了什么或者我能做些什么来解决我的问题吗？

Answer 1

在为动画站点编码Floyd算法的方式中有一个实现细节；它阻止您看到预期的结果。

下载源代码并查看Floyd.js，查看不应该存在的条件：

for (var k = 0; k < this.size; k++) {
    for (var i = 0; i < this.size; i++) {
        for (var j = 0; j < this.size; j++) {
            if (i != j && j != k && i != k) // <<== This is the problem
                ...

该算法从不通过第三个节点计算从节点到自身的路径(即i == j)，因此它从不检测循环。从本质上说，该条件假设传递到自身不能得到改进，这在主对角线设置为INFINITY时是不正确的。