Floyd多源最短路径算法

2019-07-03

概述

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
更具输入图的情况给相应的边赋值