All-pairs shortest path algorithm
问题描述
给定图
求任意两个顶点 dist[i][j]
。
算法思想
首先我们考虑这样一个问题:找到一条长度尽可能短,并且跳转尽可能少的路径。具体来说,我们要求一个数组
dist[i][j][k]
,表示在和 这两个结点之间,最多经过 个点的最短路径长度。 显然,当
时,也就是不经过任何点时, 和 之间的距离等于他们之间的边权 。 而当
时,到达 的路径可以被所有与 相连的点更新,即 图中
1
2
3
4
5
6dist[i][j] <- w[i][j]
for k = 1 to |V|:
for i in V:
for j in V:
for u in V:
dist[i][j][k] <- min(dist[i][j][k-1], dist[i][u][k-1] + w[u][j])上面的算法怎么优化?
滚动数组空间优化
dist[i][j][k] <- dist[i][u][k-1] + w[u][j]
new_dist[i][j] <- dist[i][u] + w[u][j]
我们需要最外层循环吗?
假设橙色为最短路,我们只执行一边上述循环的话,只能找到
,找不到橙色的最短路。 究其原因,是因为我们不能保证在更新
dist[i][j]
时,dist[i][ux]
和dist[ux][j]
已经是最短的。那么如果我们按照一定的顺序更新dist
数组,使得我在更新到dist[i][j]
时,所有的的前驱结点 的 dist[i][ux], dist[ux][j]
已经更新好,那么我们是不是就不需要外层循环了呢?对比一下
min(dist[i][j], dist[i][u] + w[u][j])
和 矩阵乘法的内层:dist[i][j] + dist[i][u] * w[u][j])
,发现它们有异曲同工之处矩阵乘法中,
1
2
3
4
5for k = k * 2:
for i in V:
for j in V:
for u in V:
dist[i][j][k] <- min(dist[i][j][k / 2], dist[i][u][k / 2] + dist[u][j][k / 2])
另一种解法
一条最短路径
一定包含0个或者若干个中间点。 如果我们选择点集
中前 个点 作为中间点,那么它有一条很好的性质: 如果
的最短路径中不包含 ,那么 如果
的最短路径中包含 ,那么
所以我们可以写出状态转移方程
举例说明
伪代码
1 | Floyd-Warshall(G{V,E}): |
分析算法复杂度
算法 由于算法有3层循环,循环最内部复杂度为
,所以复杂度为 调用
次 算法 没有堆优化
1次:
n次:
加入堆优化
1次:
n次:
对比两种算法的时间复杂度,
但是,