5

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

4

2 回答 2

13

经过一番思考，我想出了：

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

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

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

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] = 0then 两个参数相同，否则min()选择 的第一个参数。

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

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

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 的想法。

于 2010-01-10T21:48:53.067 回答
2

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

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

于 2010-01-10T21:40:51.393 回答