是否在Floyd-Warshall算法中重新排列外循环，因为大多数内循环会改变算法

html5 • • 问答

以下代码用于 Floyd-Warshall 算法

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

我建议将代码改写如下

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

在新代码中，我将原来的外层循环放到了最内层的循环中。我发现新代码很容易理解解决所有对最短路径问题。我的问题是：新代码是否等同于 Floyd-Warshall 算法的原始代码？

回答

不，这通常不起作用。Floyd-Warshall 算法的核心思想是找到经过较小节点子集的最短路径：1..k，然后增加该子集的大小。

在增加该子集的大小之前，必须使节点对的距离适应子集 1..k。

以维基百科上使用的示例图为例：

让我们关注从节点 3 到节点 1 的路径，它的最小权重路径为 2 + -1 + 4 = 5。

让我们运行原始算法和您的变体，看看它是否识别了这个距离：

原始（正确）算法

let d = [
    [0, Infinity, -2, Infinity],
    [4, 0, 3, Infinity],
    [Infinity, Infinity, 0, 2],
    [Infinity, -1, Infinity, 0]
];
let n = d.length;

for (let k = 0; k < n; ++k) {
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

console.log("distance from 3 to 1 = ", d[2][0]);  // 5 -- correct

您建议的算法

let d = [
    [0, Infinity, -2, Infinity],
    [4, 0, 3, Infinity],
    [Infinity, Infinity, 0, 2],
    [Infinity, -1, Infinity, 0]
];
let n = d.length;

for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
        for (let k = 0; k < n; ++k) {
            d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

console.log("distance from 3 to 1 = ", d[2][0]);  // Infinity -- wrong

以上是是否在Floyd-Warshall算法中重新排列外循环，因为大多数内循环会改变算法的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>