一、简介
$ Floyd $ 算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与 $Dijkstra$算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授 $Robert \ Floyd$ 命名。
$Floyd$ 算法是动态规划的一个例子，并在1962年由 $Robert \ Floyd$ 以其当前公认的形式出版。然而，它基本上与 $Bernard \ Roy$ 在1959年先前发表的算法和1962年 $Stephen \ Warshall$ 中找到图形的传递闭包基本相同，并且与 $Kleene$ 的算法密切相关（1956年，用于将确定性有限自动机转换为正则表达式）。算法作为三个嵌套 $for$ 循环的现代公式首先由 $Peter \ Ingerman$ 在1962年描述。
二、中心思想
路径矩阵
dis[][]：用来储存每个点到其他点的最短距离
以每个点为「中转站」，刷新所有「入度」和「出度」的距离。
遍历每一个顶点 --> 遍历点的每一个入度 --> 遍历每一个点的出度。所以时间复杂度为 $O(n^3)$ ；
以这个点为「中转站」距离更短就刷新距离（比如 $B$ 点为中转站 $AB + BD \lt AD$ 就刷新 $A$ 到 $D$ 的距离为 $AB + BD$）。
状态转移方程
$$dis[i, \ j]=min(dis[i, \ k]+dis[k, \ j], \ map[i, \ j])$$
$dis[i,j]$ 表示 $i$ 到 $j$ 的最短距离， $K$ 是穷举 $i,j$ 的断点， $dis[n,n]$初值应该为0（或根据实际情况），如果该路径不存在，应将 $dis[i,j]$ 置为 $Integer.MAX\_INT$ （或根据实际情况）。
三、算法特征
$Floyd$ 算法是一种用于求解所有节点对最短路径的动态规划算法。它适用于有向图或带权有向图，可以处理负权边，但不能处理带有负权环的图。
全局最短路径： 算法能够计算出图中任意两个节点之间的最短路径长度，即全局最短路径。
动态规划： 算法基于动态规划思想，通过不断更新中间节点，逐步得到最短路径的信息。
矩阵表示： 算法使用一个二维矩阵来存储任意两个节点之间的最短路径长度。矩阵的行和列分别对应图中的节点。
迭代更新： 算法通过多次迭代，不断更新矩阵中的元素，使其代表更短的路径长度。
三重循环： 算法的核心循环嵌套结构有三层，每一层循环都遍历所有的节点，以确定经过某个中间节点是否可以获得更短的路径。
时间复杂度： 算法的时间复杂度为 $O(V^3)$ ，其中 $V$ 是图中节点的数量。由于存在三重循环，对于大规模图来说，算法可能会相对较慢。
路径重构： 算法不仅能计算最短路径的长度，还可以通过额外的处理，得到最短路径的具体节点序列。
适用范围： 算法适用于所有类型的权值，包括负权值，但不能处理含有负权环的图，因为这会导致无限循环。
空间复杂度： 算法需要使用一个二维矩阵来存储节点间的最短路径长度，因此空间复杂度为 $O(V^2)$ ， $V$ 为节点数量。
易于实现： 尽管算法的时间复杂度相对较高，但实现相对简单，不需要像 $Dijkstra$算法那样的优先队列等数据结构。
总的来说， $Floyd$ 算法在计算图中所有节点对的最短路径时非常实用，尤其是对于小规模图或者需要计算稠密图最短路径时具有一定的优势。
四、算法实现
public static void floyd(int[][] dis, int n) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}