参考：https://blog.csdn.net/qq_35644234/article/details/60875818
一.Floyd算法的介绍
1.算法的特点：
弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理无向图或有向图或负权（仅适合权值非负的图)的最短路径问题，同时也被用于计算有向图的传递闭包。
2.算法的思路：
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P（记录最短路的路径需要，若题目不需要求路径则不需要P数组）中的元素b[i][j]，表示顶点i到顶点j经过了顶点b[i][j]。
假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。 接下来开始，对矩阵D进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。实质上是背包DP问题，最外层循环是k，表示利用前k个作为中间计算a[i][j]的最小值，本来需要三位数组a[k][i][j]，因为第k次循环只会用到a[k-1][i][j]，所以利用滚动数组，使用二维数组即可。更新N次之后，操作完成！时间复杂度为O(N^3)，空间复杂度为O(N^2)。
核心代码：
1 for(k=0;k<n;k++) 2 for(i=0;i<n;i++) 3 for(j=0;j<n;j++) 4 if(a[i][j]>a[i][k]+a[k][j]) 5 a[i][j]=a[i][k]+a[k][j],b[i][j]=b[i][k];
只有5行！现在你会发现这个看起来很高大上的算法很简单了，算是最短路的4个算法里最暴力的了！
3.实例：
题目链接：https://pintia.cn/problem-sets/1101307589335527424/problems/type/7
题意：有n种动物，m种直接转换的咒语，且转换具有传递性，求从哪一种动物到另一种的动物的最长咒语的最小值，若不能转换到所有动物，则输出0.
思路：Floyd算法的裸应用，将动物抽象为点，咒语长度抽象为边的权值，代码如下：
#include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; int n,m,a,b,c; int mp[105][105]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j) mp[i][j]=inf; while(m--){ scanf("%d%d%d",&a,&b,&c); mp[a][b]=c; mp[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(mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j]; int maxi,minv=0,res=inf; for(int i=1;i<=n;++i){ maxi=0; for(int j=1;j<=n;++j) if(mp[i][j]>maxi) maxi=mp[i][j]; if(maxi<res) res=maxi,minv=i; } if(minv) printf("%d %d ",minv,res); else printf("0 "); return 0; }