Floyd（弗洛伊德）

概述

到了如今，最短路问题已经得到了很多种解法。这些解法有相同的地方，也有不同的地方，性能也有所差异。但是，如果一种问题得出的某种解法优于其他解法太多，其他这些解法就应该随时间流逝而被逐渐淘汰。最短路问题的这些解法如今仍屹立不倒，足可说明它们各有偏重的方向。

floyd，（又称Floyd-Warshall）即弗洛伊德算法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。简单来说，是一种能够解决多源最短路的算法。但是，floyd无法处理具有负权环的图。这里提一句，floyd同样可以解决图的连通性问题。

正文

同大多数动态规划算法一样，floyd的核心代码只有短短几行。

for(int k=1;k<=n;k++)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(h[i][k]+h[k][j]<h[i][j])
            {
                h[i][j]=h[i][k]+h[k][j];
                h[j][i]=h[i][k]+h[k][j];
            }
        }
    }
}

在这几行中，却是三重循环嵌套，这导致floyd的时间复杂度达到了O(n^3)。但是，与其相对应的是floyd对于稠密图处理的简单与高效。另外，floyd对于每对起点终点枚举的查询方式，造成了它能够解决多源最短路的特性。

讲解

我们开始进行floyd整个过程的讲解。

首先，我们定义一个二维数组记录每两个点之间的距离，二维数组的大小取决于图中点的个数。这一步来构建邻接矩阵建立我们的图。我们暂定这个数组名为h。

对于这个邻接矩阵（也就是该二维数组），我们对其每一个位置进行初始化，将其初始化为一个极大值，代表两点之间无法连通。随后将题目中所给边连接，即将h数组中两点对应的位置设置成题目中所给值。如此，图中直接连通的两点所对应的位置已经不是某无穷大的值了。

需要提前处理的点都处理好了，接下来就是循环嵌套的过程。

在这个循环嵌套的过程中，我们完成三重循环，分别是枚举终点起点以及枚举它们之间的中转点（例如1-3连通而1-2以及2-3分别连通，那么2可以叫做1与3的中转点）。我们需要判断起点到终点的距离是否比通过中转点的距离更远，或者说起点到终点所需要花费的值是否大于通过中转点所花费的值。落实到公式上就是这样：

if(h[i][k]+h[k][j]<h[i][j])
{
    h[i][j]=h[i][k]+h[k][j];	//i代表起点，j代表终点，k代表中转点。
}

我们可以看出来，h数组记录的始终是当前情况下i到j的最短距离。

那么，我们的三重循环貌似应该是这样的：

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n;j++)
    {
        for(int k=1;k<=n;k++)
        {
            if(h[i][k]+h[k][j]<h[i][j])
            {
                h[i][j]=h[i][k]+h[k][j];
            }    
        }
    }
}

你可能看到我说的“貌似”二字，或者看出来了这个三重循环和我一开始写的核心代码之间的不同点。没错，这样的三重循环是不对的，而这个循环嵌套仅仅是把中转点的循环放到了内层。

这样为什么就会出错呢？我们来看看这个问题。

原核心代码是把中转点的枚举放在了最外层，我们可以分析得出来，核心代码的意愿是对于每一个中转点，分析每一对起点终点是否可以通过该中转点松弛（当然你也可以叫它优化）。这样对于每一次枚举到的中转点，每对起点终点都会被遍历一次，在最后一个中转点时，仍然还可以修改每对起点终点的最小值。

而将中转点的枚举放在最内层，我们分析得来，实现过程是对每一对起点终点枚举所有点来当作中转点。这样的话对于这对起点终点来说，属于它们的最外层循环走完之后，它们的最短距离就相对固定了，在之后的循环中再没有对它们的操作了，这会导致错误。

我们也可以这么理解：我们对于每一个新增的节点k，来判断这个k是否对于已经确定的最短路有什么影响。而随着k的增加，最终达到整张原图的大小，此时k对每条最短路的影响都已经判断完毕了，故此时得到的每两个点之间的最短路就是整张图背景下两个点之间的最短路。

我们来举几个例子帮助大家理解。（例子取自大佬博客，地址下面放出）

https://blog.csdn.net/qq_27765961/article/details/51915384

例子是取自这篇博客，但是我还是重新画一下图片吧。

第一个例子是这个样子的

若把中转点循环放在内层，过程如下：

未循环时是这样的邻接矩阵。

i=1结束之后变成了这样。

i=2结束之后还是上图那样。

这样我们就看出来了，1与2之间的距离之后的过程中就不会再更改了，而很明显我们可以从图中看出来最短距离是3。

为了保险起见，我们把中转点循环在最外层的过程也捋一遍。

仍然是这俩图。

k=1结束之后，邻接矩阵没有发生变化。

k=2的时候也是一样的。（规律好像与行列有关）

k=3即3作为中转点的时候发生了变化。

k=4之后最终的邻接矩阵变成了这样。

很明显得到了1与2之间的最短距离为3。

大家可能发现了，上面这个例子是一个有向图的例子，边只能单向通过，所以我在图中只是画了箭头，而没有画直线。那么，会不会k在内层只是在有向图中错误呢？我们用第二个例子验证一下。

我在第二个例子中只判断图的连通性，实际上简化了过程，连通则在邻接矩阵中置1，非连通则置0。

i=1时只是与4连通，而i=2的时候也只是2与4连通。你可能会说，1和2都与4连通那它们不就连通了，但是程序不知道这点，程序只知道i过了2之后，1和2的连通状态不会再改变了，并且在最后，1和2也是未连通的状态。

另外，还有几个问题。

一个是，k在最外层的话，先经历哪一个点为中转点对这个过程有影响吗？换句话说就是顺序是否对floyd产生影响。

还有一个是关于为何floyd被定义为是动态规划算法。

这两个问题在下面这篇大佬的博客中有所解释，我就不搬运了，网址放出来。

https://www.cnblogs.com/LiHior/p/7701296.html

标准代码

我假设一共n个点m条边的无向图做了一个标准代码，仅供参考。

#include<stdio.h>
#include<string.h>
#define MAX 99999999
int h[105][105];
int main()
{
    int n,m;	//n个点,m条边
    int a,b,v; 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            h[i][j]=MAX;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&v);
        h[a][b]=v;
        h[b][a]=v;
    } 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",h[i][j]);
        }
        printf("\n");
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(h[i][k]+h[k][j]<h[i][j])
                {
                    h[i][j]=h[i][k]+h[k][j];
                    h[j][i]=h[i][k]+h[k][j];
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",h[i][j]);
        }
        printf("\n");
    }
    return 0;
}

floyd的逻辑很清晰，相信大家自己也可以一步一步走出每一步的作用。另外在上面已经尝试着分析过一段核心代码了，在这里我就不对标准代码做讲解了。

例题

HDU 2544 最短路

就是一个模板的单源最短路。

题目

acm.hdu.edu.cn/showproblem.php?pid=2544

思路

就是个很普通的单源最短路，按照正常的流程，初始化，核心就可以解决。需要注意的点有一个，就是题目中说C<=1000，是不准确的，需要把最大值调整到200000。

代码

#include<stdio.h>
#define MAX 200005
int main()
{
    int n,m;
    int a,b,c;
    int h[105][105];
    while(1)
    {	
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)
        {
            break;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                h[i][j]=MAX;
            }
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            h[a][b]=c;
            h[b][a]=c;
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(h[i][j]>h[i][k]+h[k][j])
                    {
                        h[i][j]=h[i][k]+h[k][j];
                        h[j][i]=h[i][j];
                    }	
                }
            }
        }
        printf("%d\n",h[1][n]);
    }
    return 0;
}

洛谷 P2910 [USACO08OPEN]寻宝之路Clear And Present Danger

题目

https://www.luogu.org/problem/P2910

思路

首先题目中提及，a到b的危险指数不一定等于b到a的危险指数，可知是有向图。

另外，本题的输入给出了整个邻接矩阵，并且特别指出了每个岛到自己本身的危险程度为0。我们不需要对邻接矩阵赋极大的初值了。

最后，我们要在一开始记录下路线，并且在floyd核心运行完毕之后，对每一对相邻的点的危险程度进行求和。所得到的值就是最后的危险指数。

别的就没啥好说的了，就是一个很普通很裸的floyd，多源最短路嘛。

代码

#include<stdio.h>
int main()
{	
    int n,m,v;
    int sum=0;
    int a[10005];
    int h[105][105];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&v);
            h[i][j]=v;
        }
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(h[i][k]+h[k][j]<h[i][j])
                {
                    h[i][j]=h[i][k]+h[k][j];
                }
            }
        }
    }
    for(int i=1;i<=m-1;i++)
    {
        sum+=h[a[i]][a[i+1]];
        }
    printf("%d",sum);
    return 0;
}

洛谷 P2935 [USACO09JAN]最好的地方Best Spot

题目

https://www.luogu.org/problem/P2935

思路

题目一开始也是提及，连通的路都是双向边，所以是一个无向图。

据题意所说，我们需要得到每一个牧场到其他牧场的最短路，然后再求出每一个牧场到某些特定牧场最短距离的平均值最后选一个平均值最小的。也是一个典型的多源最短路，最短路的过程也不再说了。

题目中说最多500个点，却只有最多8000条边，我们把整个邻接矩阵初始化，随后记录特定的牧场都有哪些。

而在最后加和求平均值的过程中要注意，若由某牧场到某牧场本身，则跳过加和，因为距离应该为0，但实际上在一开始我们给邻接矩阵赋上了初值，无论最后有没有得到松弛，都会影响最终结果。

代码

#include<stdio.h>
#define MAX 100005
int main()
{
    int p,f,c;
    int a,b,v;
    int aver;
    int ans;
    int min=1000005;
    int want[505];
    int h[505][505];
    scanf("%d%d%d",&p,&f,&c);
    for(int i=1;i<=f;i++)
    {
        scanf("%d",&want[i]);
    }
    for(int i=1;i<=p;i++)
    {
        for(int j=1;j<=p;j++)
        {
            h[i][j]=MAX;
        }
    }
    for(int i=1;i<=c;i++)
    {
        scanf("%d%d%d",&a,&b,&v);
        h[a][b]=v;
        h[b][a]=v;
    }
    for(int k=1;k<=p;k++)
    {
        for(int i=1;i<=p;i++)
        {
            for(int j=1;j<=p;j++)
            {
                if(h[i][k]+h[k][j]<h[i][j])
                {
                    h[i][j]=h[i][k]+h[k][j];
                    h[j][i]=h[i][j];
                }
            }
        }
    }
    for(int i=1;i<=p;i++)
    {
        aver=0;
        for(int j=1;j<=f;j++)
        {
            if(i!=want[j])
            {
                    aver+=h[i][want[j]];
            }	
        }
        if(aver<min)
        {
            min=aver;
            ans=i;
        }
    }
    printf("%d",ans);
    return 0;
}

洛谷 P2888 [USACO07NOV]牛栏Cow Hurdles

题目

https://www.luogu.org/problem/P2888

思路

这道题的floyd稍微有一点隐晦，没有直接指出最短路，而是一条路上最大的花费等于这条路的花费，不断松弛找到每两个点之间最高的栏（最大的花费）的最小值（最大花费最小的那条路）。

做这道题我们只需要把floyd的核心代码中的判断稍微修改一下。

题目中提及单向路径，故是一个有向图。

题目中给出了多个任务，故也可以看出是一个多源问题。

最后，有可能无法到达，也就是无法满足任务，输出-1，我把这里定成了栏的高度大于某个值就不满足，因为我在初始化时，用了一个极大值来记录无法通过的路径。

代码

#include<stdio.h>
#define MAX 1000010
int max(int a1,int b1)
{
    if(a1>b1)
    {
        return a1;
    }
    else
    {
        return b1;
    }
}
int main()
{
    int n,m,t;
    int a,b,c;
    int h[305][305];
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            h[i][j]=MAX;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        h[a][b]=c;
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(max(h[i][k],h[k][j])<=h[i][j])
                {
                    h[i][j]=max(h[i][k],h[k][j]);
                }
            }
        }
    }
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d",&a,&b);
        if(h[a][b]<=1000000)
        {
            printf("%d\n",h[a][b]);
        }
        else
        {
            printf("-1\n");
        }
    }
    return 0;
}

未完待续…