Floyd 算法的本质是动态规划

基本要点

1. 时间复杂度是O(n^3)O(n3)，所以，只适用于n<500n<500这种结点数不多的情况。
2. 它是多源最短路，可以在任何两点之间找到最短路。
3. 支持负边权
4. 可以判断图中是否存在负回路

代码：

#includeusingnamespacestd;intg[N][N];intdis[N][N];// dis[i][j]: i->j 最短距离

/*

证明：定义 dis[i][j][k] 表示从 i 到 j 的可以经过 1~k 这个问题可以分解为两个子问题

（1）不经过 k 号结点，即 dis[i][j][k-1]

（2）经过 k 号结点，即 dis[i][k][k-1]+dis[k][j][k-1];

因此，有：

dis[i][j][k] = min(dis[i][j][k-1], dis[i][k][k-1], dis[k][j][k-1]);

上式中第三维 k 可以省略，则有：

dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

虽然 i,j,k 的顺序不保证，导致上式中 dis[i][k] 和 dis[k][j] 可能是已经被更新过的 dis[i][k][k] 和 dis[k][j][k] 了，

但是这并不影响其正确性。因为更新后的值一定会变得更小，不会影响最终结果。

*/ 

int main(){

    int n;

    cin >> n;

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= n; j++)

        {

            cin >> g[i][j];

            dis[i][j] = g[i][j];

        }

    // floyd 求任意两点间的最短路径

    for(int k = 1; k <= n; k++)   // 枚举中间点

        for(int i = 1; i <= n; i++)

            for(int j = 1; j <= n;j++)

                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

                

    // 判断负环

    for(int i =1; i <= n; i++)

    {

        if(dis[i][i] < 0)

            cout<<"存在负环";

        break;

    }       

    return 0;}

Copy

证明：

定义 dis[i][j][k]dis[i][j][k] 表示从 ii 到 jj 的可以经过 11~kk 号结点的最短路径，此问题可以被分解为两个子问题

1. 不经过 kk 号结点，即 dis[i][j][k-1]dis[i][j][k−1]
2. 经过 kk 号结点，即 dis[i][k][k-1]+dis[k][j][k-1]dis[i][k][k−1]+dis[k][j][k−1]

因此，有：
dis[i][j][k] = min(dis[i][j][k-1], dis[i][k][k-1], dis[k][j][k-1]);dis[i][j][k]=min(dis[i][j][k−1],dis[i][k][k−1],dis[k][j][k−1]);
上式中第三维 k 可以省略，则有：
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
虽然去掉一维后，i,j,ki,j,k 的顺序不保证，导致上式中 dis[i][k]dis[i][k] 和 dis[k][j]dis[k][j] 可能是已经被更新过的 dis[i][k][k]dis[i][k][k] 和 dis[k][j][k]dis[k][j][k] 了，但是这并不影响其正确性。因为更新后的值一定会变得更小，不会影响最终结果。

Floyd 算法为什么把k放在最外层？

采用动态规划思想，f[k][i][j]f[k][i][j] 表示 ii 和 jj 之间可以通过编号不超过 kk，即编号 1,2,...,k1,2,...,k 的节点的最短路径。初值 f[0][i][j]f[0][i][j] 为原图的邻接矩阵。

则该问题可以划分为两个子问题：

f[k][i][j]f[k][i][j] 可以从 f[k-1][i][j]f[k−1][i][j] 转移来，表示 ii 到 jj 不经过 kk 这个节点。

也可以从 f[k-1][i][k] + f[k-1][k][j]f[k−1][i][k]+f[k−1][k][j] 转移过来，表示经过 kk 这个点。

于是：f[k][i][j] = \min (f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])

然后你就会发现 ff 最外层一维空间可以省略，因为 f[k][][]f[k][][] 只与 f[k-1][][]f[k−1][][] 有关，虽然省略后，无法确定 k,i,jk,i,j 的关系，但是 f[k][i][k]f[k][i][k] 和 f[k][k][j]f[k][k][j] 是由 f[k-1][i][k]f[k−1][i][k] 和 f[k-1][k][j]f[k−1][k][j] 计算而来，因此前者一定小于等于后者，省略后再取最小值并不会影响最终结果的正确性。

练习题

• P2779 奶牛跨栏(Cow Hurdles)
• P2370 平面最短路径问题