我们来谈谈Floyd是如何找到图的最短路径的？计算多源最短路径。在单源正权重的最短路径中，我们会使用Dijkstra算法寻找最短路径，算法的思想很简单——贪心算法：每次确定最短路径的一个点，然后维护（update)这个点附近的点的距离加入预选Queue，等待下一次抛出被确认。虽然想法很简单，但是实现起来却非常复杂。我们需要一个邻接矩阵（表）来存储长度，需要一个优先级队列（或者每次比较）来维护一组预选点。还需要用一个boolean数组来标记是否已经确认，而且……总之Dijkstra算法的思想很容易接受，但是实现起来其实很麻烦。但是单源最短路径没有有效的求解方法，复杂度也是O(n2)。但是，如果要在一个n点图中求多个源的最短路径，从Dijkstra算法的角度来看，需要执行Dijkstran次才能得到所有点之间的最短路径，但是可以执行Dijkstra算法n次次，复杂度为O.(n3)。但是这样感觉很臃肿，代码量巨大，占用空间和内存也很大。有什么办法稍微改变一下味道吗？答案是肯定的，今天就带大家来了解一下牛逼的Floyed算法。算法介绍什么是Floyed算法？Floyd算法，也称为插值法，是一种利用动态规划的思想在给定的带权图中寻找多个源点之间最短路径的算法，类似于Dijkstra算法。该算法的名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学教授罗伯特·弗洛伊德(RobertFloyd)的名字命名。简单来说，算法的主要思想是动态规划（dp），求最短路径需要不断的松弛（熟悉spfa算法的人可能对松弛不陌生）。而算法的具体思路是：1.邻接矩阵（二维数组）dist存储路径，数组中的值开始表示点之间的初始直达路径，最后是最小路径点之间。有两点需要注意，第一个是如果没有两个点直接相连，那么默认取一个大的值（不要做成负数会计算溢出），第二个是自己和自己之间的距离应该是0。2.从第1点到第n点依次加入松弛计算，每一个点都加入测试枚举路径长度是否有变化（路径是否可以自己更新).当依次添加（k个枚举）个松弛点时，需要遍历图（i，j双循环）中的每个点对，判断每个点对的距离是否因添加点而产生的距离变化最小，如果它发生变化（变化很小），然后两点(i,j)之间的距离发生变化。2.重复以上直到完成最后一个点插入测试。第二步的状态转移方程为：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])其中dp[a][b]的意思可以理解为a点到b点的最短路径，所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]表示从k到j路径的最短路径。让我们来说明一个案例。在初始情况下，每个点只知道与自己直接相连的点的距离，而其他间接相连的点不知道距离。例如，A-B=2，A-C=3，但不计算B-C。长度未知。添加第一个节点A进行更新计算。可以发现，由于加入了A，原本不相连的B、C点对和B、D点对变成了相连，加入A后的距离是当前的最小值。同时你可以发现，加入A也让C-D多了一条联通路径（6+3），但是C-D联通的距离是9，远大于原来的（C,D）联通路径2，所以这个就不更新了。我们继续添加第二个节点B，这个点和前面的A执行同样的操作，更新一些点。因为有很多点连接到B，所以可以生成很多新的路径。这里我将它们一一列举并加以说明。在这里，我将使用1表示新路径，使用0表示原始长度。AF1=AB+BF=6+2=8AC0(3)不更新AD1=AB+BD=2+8=10>AD0(6)不更新...更多路径在此不再列举。在后面的序列中添加C、D、E、F也是同样的操作，最后全部添加完就没有更新的路径了，结束就停止了。其实此时画面中的联系更多了。这些链接代表当前的最短路径。这也符合我们的需求，我们最终想要的是所有节点的最短路径。每个节点最终应该有5条边指向不同的节点！矩阵对应的边值就是点之间的最短路径。至于算法的模拟，两个核上面已经讲过了，剩下的大家可以自己模拟。程序实现对于程序来说，插入过程是相当简单的。核心代码只有四行！这种写法适用于有向图和无向图，无向图的算法优化后面会讲到。代码如下publicclassfloyd{staticintmax=66666;//Intege.max不加2越界为负publicstaticvoidmain(String[]args){intdist[][]={{0,2,3,6,max,max},{2,0,max,max,4,6},{3,max,0,2,max,max},{6,max,2,0,1,3},{max,4,max,1,0,max},{max,6,max,3,max,0}};//映射//6for(intk=0;k<6;k++)//添加thekthnodeforcalculation{for(inti=0;i<6;i++)//每加一个点都要枚举图看有没有可以更新的{for(intj=0;j<6;j++){dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);}}}//输出为(inti=0;i<6;i++){System.out.print("节点"+(i+1)+"最短路径");for(intj=0;j<6;j++){System.out.print(dist[i][j]+"");}System.out.println();}}}执行结果为：可自行计算，图形与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内的相邻城市分别为：City0->[City1,City2]City1->[City0,City2,City3]City2->[City0,City1,city3]city3->[city1,city2]城市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内的相邻城市分别为：City0->[City1]City1->[City0,City4]City2->[City3,City4]City3->[City2,City4]City4->[City1,City2,City3]City0在阈值距离2内只有1个相邻城市。提示：2<=n<=1001<=edges.length<=n*(n-1)/2edges[i].length==30<=fromi
