Floyd多源最短路径算法
概述
Floyd 算法是一种利用动态规划的思想、计算给定的带权图中任意两个顶点之间最短路径的算法。相比于重复执行多次单源最短路算法,Floyd 具有高效、代码简短的优势,在解决图论最短路题目时比较常用。
我们用 dp[k][i][j]
表示 i 到 j 能经过 1~ k 的点的最短路。那么实际上dp[0][i][j]
就是原图,如果 i, j之间存在边,那么 i , j之间不经过任何点的最短路就是边长,否则,i, j之间的最短路为无穷大。
那么对于 i, j 之间经过 1 ~ k 的最短路 dp[k][i][j]
可以通过经过 1 ~ k - 1 的最短路转移过来。
- 如果不经过第 k个点,那么就是
dp[k - 1][i][j]
。 - 如果经过第 k 个点,那么就是
dp[k - 1][i][k] + dp[k - 1][k][j]
。
所以就有转移
$\displaystyle dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j])$
示例代码
int g[N][N]; // 邻接矩阵存图
int dp[N][N][N];
void floyd(int n) {
for (int k = 0; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (k == 0) {
dp[k][i][j] = g[i][j];
} else {
dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
}
}
}
}
}
仔细分析,dp[k]
只能由 dp[k-1]
转移过来。并且 dp[k - 1][i][k] = dp[k][i][k]
,因为 i 到 k 的最短路中间肯定不会经过 k。同理,dp[k - 1][k][j] = dp[k][k][j]
。
那么转移实际上变成了
$\displaystyle dp[k][i][j] = min(dp[k - 1][i][j], dp[k][i][k] + dp[k][k][j])$
这时候,我们尝试把 k这一维去掉,就用 dp[i][j]
来表示 i, j之间的最短路,那么转移变成了
$\displaystyle \forall{1 \le k \le n} \ \ \ dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])$
这时候,dp 数组就已经退化成为 g 数组了。
我们写出最终的 Floyd 的形式,这也是常用的写法,优化了一维的空间。并且写法更加简单。如果理解了动态规划的思想,你就一定明白了为什么枚举的中间点 k 一定要写在最外面。没有理解这一点,很容易把 3 个循环的顺序弄错了。
刚才分析得出,最后的 dp 数组退化成了 g 数组,所以可以直接在原数组上操作。
int g[N][N];
void floyd(int n) {
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
算法的时间复杂度 O(n^3) ,空间复杂度 O(n^2)
floyd 是用邻接矩阵,初始化分为3步:
- 全部初始化为 INF
- 将从自己到自己的点初始化为0, 即正对角线上为0
- 更具输入图的情况给相应的边赋值