优化对称邻接矩阵的Floyd-Warshall算法

Question

优化对称邻接矩阵的Floyd-Warshall算法

algorithmfloyd-warshall

5

如果保证有一个对称的邻接矩阵，是否存在一种优化方法可以降低 Floyd-Warshall 算法的运行时间常数？

- JPvdMerwe

它不总是对称的吗？O_o - P Shved

2

有时候你可能会有有向边，那么它就不对称了。 - JPvdMerwe

2个回答

2

（使用维基百科文章中的伪代码符号）我认为（但尚未测试），如果edgeCost矩阵是对称的，则在每次迭代后，路径矩阵也将是对称的。因此，您只需要在每次迭代中更新一半的条目。

在较低层次上，您只需要存储矩阵的一半（因为d(i,j) = d(j,i)），因此可以减少内存使用量，并希望减少缓存未命中次数，因为您将多次访问相同的数据。

- celion

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JPvdMerwe · Accepted Answer

经过一些思考，我想出了以下方案：

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 证明

输入矩阵是对称的。现在剩下的证明使用修改过的 Floyd-Warshall 证明来展示两个内部循环的计算顺序无关紧要，且每一步后图形依然保持对称。如果我们能够展示这两个条件都成立，那么这两种算法就做同样的事情。

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

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]不能为负数（否则在图中会有一个负环），这意味着dist[i][k][k] = dist[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在它们的路径中都无关紧要。由于dist[i][j][k-1]仅用于计算dist[i][j][k]，所以在计算dist[i][j][k]之前，dist[i][j]将保持为矩阵中的dist[i][j][k-1]。如果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提供的想法。