1.什么是Floyd算法？
首先同样从百度百科的介绍来看
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
2.Floyd和Dijkstra的区别
既然是最短路算法，那就不可避免的要与dijkstra进行比较
1.Floyd是多源汇最短路算法，dijkstra单源汇最短路
什么是多源汇最短路呢？也就是求得是任意两点之间的最短路径，而dijkstra求得是起点到其余点的最短路径
2.Floyd的复杂度更高
因为Floyd求得是任意两点之间的最短路径，理所当然它的时间复杂度非常高，达到了O（n^3），n是图中点的数量。而朴素的dijkstra是O(n^2)。
3.Floyd的原理不同
Floyd基于的是动态规划的思想完成的算法，而Dijkstra是以贪心为思想的。
4.Floyd可以解决带负权边的最短路
Floyd无论图中是否带负权都是可以使用的，而Dijkstra只能解决带正权边的最短路问题。
3.Floyd的优缺点
从上面的对比中我们很容易看出来，Floyd是一个效率很低的算法，为什么呢？因为它就只有三个for循环 😂。所以这个算法是非常容易记忆的。因为它的时间复杂度非常高，所以在常数n一大的情况下，Floyd是不可取的了。
4.Floyd的核心流程（3个for循环）
首先我们Floyd算法使用的是邻接矩阵g[i][j]存储图。g[i][j]表示的是点i到点j的最短路径。
初始化操作：
for(int i=1;i<=n;++i){ //任意两点之间初始化为正无穷 Arrays.fill(g[i],INF); //自己到自己的距离是0 g[i][i]=0; }
动规的状态表示：
d[k][i][j]:从i点到j的路径中，只经过1~k这些点的最短路径 其中第一维度可以优化掉
核心代码逻辑：
//基于动规的思想 for (int k = 1; k <=n; k++) { for (int i = 1; i <=n; i++) { for (int j = 1; j <=n; j++) { //类似之前我们的松弛操作 g[i][j]=Math.min(g[i][j], g[i][k]+g[k][j]); } } }
5.Floyd的注意事项
Floyd算法是可以处理带负权的情况，但是不可以带负权回路，原理同bellman-ford算法中讲的一样。Floyd的效率极低，达到n^3，除非数据量特别小或者题意不得不使用Floyd算法，大家还是尽量少使用，避免TLE。
6.Floyd的课后习题
1.牛的比赛
题目链接：牛的比赛https://www.acwing.com/problem/content/description/4247/
题目分析:
这道题并不是我们常见的最短路径模型题目，但我们可以抽象成一个多源BFS模型。首先我们先思考一个问题——如何确定一头牛是否可以确定排名？
答案能得到该牛和其他所有牛的的战斗力关系。
因为Floyd本身就是基于动态规划的思想，所以这里我们也是结合到了动态规划。
状态表示:f[i][j]==1表示i的战斗力大于j 状态转移方程:f[i][j]|=(f[i][k]&f[k][j]);
如何理解状态转移方程呢？
比如我们现在有两头牛i,j。题目并没有直接告诉我们i的战斗力大于j。但是如果我们能从a和b之外的牛找到一头牛k，f[i][k]==1说明i的战斗力大于k，f[k][j]说明k的战斗力大于j。这两个条件都满足是不是就能说明i的战斗力大于j了，所以f[i][j]可以更新为1。
代码转换：
import java.util.Scanner; public class Main { static int N=110; //记 f[i][j] 表示 i 的排名在 j 之前 static int[][] f=new int[N][N]; static int n,m; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); for (int i = 0; i < m; i++) { int a=sc.nextInt(); int b=sc.nextInt(); //a在b前面 f[a][b]=1; } for (int k = 1; k <=n; k++) { for (int i = 1; i <=n; i++) { for (int j = 1; j <=n; j++) { f[i][j]|=(f[i][k]&f[k][j]); } } } int res=0; for (int i = 1; i <=n; i++) { int ans=0; for (int j = 1; j <=n; j++) { //只有f[i][j]和f[j][i]有一个为1说明两者都是有关系的 if (f[i][j]==1||f[j][i]==1) ans++; } //当i和其他所有的牛都有关系，说明i的位置可以确定 if (ans>=n-1) res++; } System.out.println(res); } }
