algorithm - 针对对称邻接矩阵优化 Floyd-Warshall

Question

如果保证具有对称邻接矩阵，是否存在降低 Floyd-Warshall 运行时常数因子的优化？

Answer 1

经过一番思考，我想到了:

for (int k = 0; k < N; ++k)
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

当然，现在我们都需要证明它是正确且更快的。

正确性更难证明，因为它依赖于 Floyd-Warshall 的非平凡证明。这里给出了一个很好的证明:Floyd-Warshall proof

输入矩阵是symmetric .现在，其余证明使用修改后的 Floyd-Warshall 证明来表明 2 个内部循环中的计算顺序无关紧要，并且图保持对称每一步之后。如果我们证明这两个条件都成立，那么两种算法都会做同样的事情。

让我们将 dist[i][j][k] 定义为从 i 到 j 的距离，仅使用集合中的顶点{0, ..., k} 作为从 i 到 j 路径上的中间顶点。

dist[i][j][k-1] 定义为从 i 到 j 的边的权重。如果两者之间没有边，则该权重被视为无穷大。

现在使用与上面链接的证明相同的逻辑:

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

现在在计算 dist[i][k][k](对于 dist[k][i][k] 也是如此):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1])

现在由于 dist[k][k][k-1] 不能为负(或者我们在图中有一个 negative loop)，这意味着 dist[ i][k][k] = 距离[i][k][k-1]。因为如果 dist[k][k][k-1] = 0 则两个参数相同，否则选择 min() 的第一个参数。

所以现在，因为dist[i][k][k] = dist[i][k][k-1]，在计算dist[i][j]时[k] dist[i][k] 或 dist[k][j] 是否已经允许 k 并不重要code> 在他们的路径中。由于dist[i][j][k-1]仅用于dist[i][j][k]的计算，dist[ i][j] 将在矩阵中保持 dist[i][j][k-1] 直到 dist[i][j][k] 计算得出。如果 i 或 j 等于 k 则上述情况适用。

因此，计算的顺序无关紧要。

现在我们需要在算法的所有步骤之后证明 dist[i][j] = dist[j][i]。

我们从一个对称网格开始，因此 dist[a][b] = dist[b][a]，对于所有 a 和 b.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
           = min(dist[j][i], dist[k][i] + dist[j][k])
           = min(dist[j][i], dist[j][k] + dist[k][i])
           = dist[j][i]

因此，我们的赋值既为真，也将保持 dist[a][b] = dist[b][a] 不变。因此 dist[i][j] = dist[j][i] 在算法的所有步骤之后

因此，两种算法都会产生相同的正确结果。

速度更容易证明。内部循环的调用次数是正常调用次数的一半多一点，因此该函数的速度大约是正常调用次数的两倍。只是稍微慢了一点，因为您仍然分配了相同的次数，但这并不重要，因为 min() 占用了您大部分时间。

如果您发现我的证明有任何问题，无论技术性如何，请随时指出，我会尝试修复它。

编辑:

您可以通过这样更改循环来加快速度并节省一半的内存:

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

这只是将优化算法的上述 for 循环分开，所以它仍然是正确的，并且它可能会获得相同的速度，但使用一半的内存。

感谢 Chris Elion 的想法。