一、前言

在之前的图论算法中有说过基本都是从一个原点出发，然后定义其他点到原点的一个距离最小值。那假设这个原点都是不固定的，而题目刚好要求去求任意两个点之间的最小距离的话，那么这个时候暴力美学就非常凸显出其独有的重要性了。那么本章总结的Floyd算法，就是能够解决这样的问题。

二、题目汇总

①Floyd算法模板(ACwing.854)

相关分析

时间复杂度: $O(n^3)$

适用场景: 当点的数量很少，而边的数量较多的稠密图，且题目要求求的是任意两点之间的最短距离的时候，就可以利用此算法进行求解。

思路: 由于是稠密图，可以用邻接矩阵来存图，对于每个邻接矩阵，都是会有$g[a][b]$表示a到b的距离，那么一旦a到b之间这条路径有其他点k的话，那么就可以考虑用k这个点去尝试更新一下$g[a][b]$之间的距离，也就是:
$$g[a][b]=min(g[a][b],g[a][k]+g[k][b])$$
这样的话，我们利用三层循环，内两层循环去循环a,b两个点，外一层循环，循环k这个点这样就可以不重不漏的列举每个路径的可能性，对于无边的边，初始化为正无穷，就可以实现更新了。

完整AC代码

#include 
#include 
#include 

using namespace std;

const int INF = 1e9;
const int N = 205;
int n, m, k;
int grid[N][N];

void floyd() {
    for(int k = 1; k <= n; k ++ ) {
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= n; j ++ ) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    //初始化
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= n; j ++) {
            if(i == j) grid[i][j] = 0;
            else grid[i][j] = INF;
        }
    }
    
    for(int i = 1; i <= m; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        
        grid[a][b] = min(grid[a][b], c);
    }
    
    floyd();
    
    while(k -- ) {
        int x, y;
        cin >> x >> y;
        
        if(grid[x][y] > INF / 2) cout << "impossible" << endl;
        else cout << grid[x][y] << endl;
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

相关问题

循环的顺序能不能变？

在上面的代码，我们可以看到，循环的顺序是先循环k，再循坏i，j。也就如下

void floyd() {
    for(int k = 1; k <= n; k ++ ) {
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= n; j ++ ) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9

如果把k这一层放到最内层，如下的话可以吗？

void floyd() {
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= n; j ++ ) {
            for(int k = 1; k <= n; k ++ ) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9

答案是不行的！

首先举个例子，假设有一组样例是这样的

10 4 1

2 8 1

8 9 8

9 1 10

1 10 0

2 10

上面的样例，显然从2到10的距离最短是19，但是如果按照第二种方式，最后得到的结果会是impossible的，为什么呢？从循环顺序来看，当我们要求$ g[2][10]$的时候就需要求$g[2][1]$,而在求$g[2][1]$的时候，我们发现$g[2][1]是通过g[2][9]和g[9][1]得到的 $，而如果循环把k放到内层，那么$g[2][9]$会在i=2，j=9的时候才能推出来，这样就导致$g[2][1]$不能顺利得到正确结果，也就是最后得不到一条2到10的最短距离。

其次我们应该用动态规划的思想去理解Floyd的算法。我们可以让这个算法的动态规划数组看成$f(k,i,j)$代表以前k个点为媒介的时候，从i到j这个点的最短距离。

利用dp分析的方法有下面这个图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4rDX2o1b-1659155399898)(C:/Users/0604520/AppData/Roaming/Typora/typora-user-images/image-20220730101206077.png)]

动态规划转移方程如下:
$$f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])$$
也就是说，我们当前第k层的状态应该根据上一层已经推出的k-1层来进行运算，所以k这一层循环应当放在最外面。

而由于上一层推出来的一个数据本身就可以用来推导下一层，就和背包dp问题的感觉一样，就可以优化一层，利用滚动数组的感觉，变成二维的dp解法，也就是我们的解法一。

②未完待续