前言在3358www.Sina.com/中，在路径搜索的最短路径上除了Dijkstra算法外，Floyd算法也非常经典，但两种算法有区别，Floyd主要是3358 www.sinn
使用3358www.Sina.com/Dijkstra算法查找最短路径。 而且算法的思想很简单。 — 图论:每次确定最短路径的一个点，保持(更新)该点周围的点的距离，加入预选队列，等待下一次抛出确定。 虽然思想简单，实现起来非常复杂，但我们需要在矩阵(表)旁边保存长度，需要优先队列(或每次比较)来维持预选点的集合。 你确定要用布尔数组标记吗？ 另外……
总之，是Dijkstra算法的计算多源最短路径，但在单源正权值最短路径。 但是，单源最短路径的解还没有有效的方法，复杂度也是o(n2 )。
另一方面，如果想在n点图表中求出多源最短路径，如果是贪心算法，则为了得到所有点间的最短路径，需要执行n次Dijkstra，但执行n次Dijkstra算法但是，如此庞大，代码量巨大，消耗了很多空间内存。 有稍微改变味道的方法吗？
有答案。 今天带大家来了解一下牛吼的Floyed算法吧。
算法是什么是流动算法？
Floyd算法又称插值法，是利用动态规划思想在给定加权图中寻找多源点之间最短路径的算法，与戴克斯特拉法相似。 该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授sxdlr命名。
简言之，算法的主要思想是思想上是很容易接受，寻求最短路径需要不断松弛(熟悉spfa算法的可能更熟悉松弛)。
算法的具体思路是
1 .相邻矩阵(二维数组) dist存储路径，数组中的值开始表示点与点之间的初始直接路径，最终表示点与点之间的最小路径。 有两点需要注意。 第一，如果没有直接连接的两点，则缺省值为较大(避免计算中溢出负数)；第二，自己和自己的距离为0。
2 .从第一到第n个顺序进行松弛计算，对每个点进行实现上其实是非常麻烦枚举，路径长度是否发生了变化，是否可以自己更新路径？ 在(k枚举)中按顺序添加松弛点时，需要从Dijkstra算法的角度上，判断各点对距离为动态规划(dp)，发生变更)时，两点) I、j )距离发生变更
2 .上文试探
其中遍历图中每一个点对(i,j双重循环)为：
DP[I][j]=min(DP[I][j]，dp[i][k] dp[k][j] )这里dp[a][b]的意思可以理解为从点a到点b的最短路径，因此dp[i][k]
让我们来图解一下初期的情况吧。 每个点只知道与自己直接相连的点的距离，而其他间接相连的点还不知道距离。 例如，A-B=2，A-C=3，但B-C不经过计算就不知道长度。
添加第一个节点a进行更新计算时，可以看到a的添加将原本不连接的b、c点对和b、d点对连接起来，再添加a之后的是否因为加入的点而发生最小距离变化。 同时，添加a后，C-D可以建立多条连接路径(6)，但与C-D连接的距离远大于9
继续加入第二个节点b吧。 这一点进行与前面的a相同的操作。 更新几点。 因为和b相连的地方很多，所以会产生很多新的路径。 在这里列举说明。 这里统一用1表示新路径，用0表示原始长度。
用af1=abbf=62=8af0(更新
用AE1=abbe=24=6AE0(进行更新
以CE1=CBbe=5(9ce0()更新
用cf1=cbbf=56=11cf0(更新
用ef1=EBBF=46=10ef0(更新
当然，还有比现有路径更大的新路径。 例如，以下情况：
AC1=ABBC=25=7AC0(3)直到最后插点试探完成。
ad1=abBD=28=10ad0(6)第2步的状态转移方程
.
我不会在这里列举更多的传球。
以后添加c、d、e、f是相同的操作，最终全部添加完毕，如果路径无法更新，停止就结束。 其实这个时候，图中的连接变多了。 这些连接都是i到k的最短路径
前的最短路径。 这也和我们的需求贴合，我们最终要的是所有节点的最短路径。每个节点最终都应该有5条指向不同节点的边！ 矩阵对应边值就是点点之间最短路径。至于算法的模拟两部核心已经告诉大家了，大家可以自行模拟剩下的。
程序实现而对于程序而言，这个插入的过程相当简单。核心代码只有四行！ 这个写法适合有向图和无向图，无向图的算法优化后面会说。
代码如下
执行结果为：
可以自行计算，图和上篇的Dijkstra用的图是一致的，大家可以自行比对，结果一致，说明咱么的结果成功的。
当然，在你学习的过程中，可以在每加入一个节点插入完成后，打印邻接矩阵的结果，看看前两部和笔者的是否相同(有助于理解)，如果相同，则说明正确！
对于加入点更新你可能还是有点疑惑其中的过程，那咱么就用一个局部来演示一下帮助你进一步理解Floyd算法，看其中AB最短距离变化情况祝你理解：
自己会没会？刷一道题就可以知道了，刚好力扣1334是一道Floyd算法解决的问题。
题目描述为：
有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。
注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
示例1：
输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2]
城市 1 -> [城市 0, 城市 2, 城市 3]
城市 2 -> [城市 0, 城市 1, 城市 3]
城市 3 -> [城市 1, 城市 2]
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。
示例2：
输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1]
城市 1 -> [城市 0, 城市 4]
城市 2 -> [城市 3, 城市 4]
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3]
城市 0 在阈值距离 2 以内只有 1 个邻居城市。
提示：
2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
所有 (fromi, toi) 都是不同的。
思路分析：
拿到一道题，首先就是要理解题意，而这道题的意思借助案例也是非常能够理解，其实就是判断在distanceThreshold范围内找到能够到达的最少点的编号，如果多个取最大即可。正常求到达最多情景比较多这里求的是最少的，但是思路都是一样的。
这道题如果使用搜索，那复杂度就太高了啊，很明显要使用多源最短路径Floyd算法，具体思路为;
1 .先使用Floyd算法求出点点之间的最短距离，时间复杂度O(n3)
2 . 统计每个点与其他点距离在distanceThreshold之内的点数量，统计的同时看看是不是小于等于已知最少个数的，如果是，那么保存更新。
3 .返回最终的结果。
实现代码：
class Solution { public int findTheCity(int n, int[][] edges, int distanceThreshold) { int dist[][]=new int[n][n]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++){ //保证数据比最大二倍大(两相加不能比它大)，并且不能溢出，不要Int最大 相加为负会出错 dist[i][j]=1000000; } dist[i][i]=0; } for(int arr[]:edges){ dist[arr[0]][arr[1]]=arr[2]; dist[arr[1]][arr[0]]=arr[2]; } for(int k=0;k<n;k++){ for(int i=0;i<n;i++) { for(int j=0;j<n;j++){ dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } int min=Integer.MAX_VALUE; int minIndex=0; int pathNum[]=new int[n];//存储距离 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(dist[i][j]<=distanceThreshold){ pathNum[i]++; } } if(pathNum[i]<=min) { min = pathNum[i]; minIndex=i; } } return minIndex; }}那么想一下优化空间：Floyd算法还有优化空间嘛？
有的，这个是个无向图，也就是加入点的时候枚举其实会有一个重复的操作过程(例如枚举AC和CA是效果一致的)，所以我们在Floyd算法的实现过程中过滤掉重复的操作，具体代码为：
class Solution { public int findTheCity(int n, int[][] edges, int distanceThreshold) { int dist[][]=new int[n][n];//存储距离 for(int i=0;i<n;i++) { for(int j=0;j<n;j++){ dist[i][j]=1000000; } dist[i][i]=0; } for(int arr[]:edges){ dist[arr[0]][arr[1]]=arr[2]; dist[arr[1]][arr[0]]=arr[2]; } for(int k=0;k<n;k++){ for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++){//去掉重复的计算 dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); dist[j][i]=dist[i][j]; } } } int min=Integer.MAX_VALUE; int minIndex=0; int pathNum[]=new int[n];// for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(dist[i][j]<=distanceThreshold){ pathNum[i]++; } } if(pathNum[i]<=min) { min = pathNum[i]; minIndex=i; } } return minIndex; }} 尾声对于Floyd算法，如果初次接触不一定能够理解这个松弛的过程。
Floyd像什么呢，最终最短路径大部分都是通过计算得到而存储下来直接使用的，我觉得它和MySQL视图有点像的，视图是一个虚表在实表上计算获得的，但是计算之后各个数据就可以直接使用，Floyd是在原本的路径图中通过一个动态规划的策略计算出来点点之间的最短路径。
Floyd和Dijkstra是经典的最短路径算法，两者有相似也有不同。在复杂度上，Dijkstra算法时间复杂度是O(n2),Floyd算法时间复杂度是O(n3)；在功能上，Dijkstra是求单源最短路径，并且路径权值不能为负，而Floyd是求多源最短路径，可以有负权值；算法实现上，Dijkstra 是一种贪心算法实现起来较复杂，Floyd基于动态规划实现简单；两个作者Dijkstra和Floyd都是牛逼轰轰的大人物，都是图灵奖的获得者。
除了Floyd算法，堆排序算法heapSort也是Floyd大佬发明的，属实佩服！
Floyd算法，俗称插点法，不就一个点一个点插进去更新用到被插点距离嘛！
好啦，Floyd算法就介绍到这里，如果对你有帮助，请动动小手点个赞吧！蟹蟹。