如果保证有一个对称的邻接矩阵,是否存在一种优化方法可以降低 Floyd-Warshall 算法的运行时间常数?
如果保证有一个对称的邻接矩阵,是否存在一种优化方法可以降低 Floyd-Warshall 算法的运行时间常数?
经过一些思考,我想出了以下方案:
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提供的想法。