建设工程协会网站查询系统阿里云网站域名备案
求最短路径，一般有三种方法：
单源最短路径--Dijkstra算法
此算法只能求不带负权值的有向无环图
单源最短路径--Bellman-Ford算法（少考）
此算法优点在于：可以求带权值的右向无环图
但只是缺点明显，时间复杂度很高，相当于暴力求解。
多源最短路径--Floyd-Warshall算法
此算法可以解决任意两点间的最短路径，也可以求带负权值的右向无环图。
单源的意思是只能从指定位置开始，求其他位置的最短路径。
多源则不同，可以求任意两点间的最短路径。
本文章主要讲解floyd算法。
floyd算法逻辑：
想要理解floyd算法的实现逻辑，最形象的视频讲解是很有必要的。
这里小编极力推荐B站蓝不过海呀这个Up的视频讲解，讲的非常细节，
比自己去看一些什么算法导论效率要高的多，毕竟相较于文字，
人对图形化的东西更有印象。
B站连接：图-最短路径-Floyd(弗洛伊德)算法
视频中只是对算法的逻辑进行了讲解，但是没有涉及代码的实现，接下来，
我会依照视频讲解逻辑，补充一个JAVA代码的实现方式，文章末尾附带源码。
代码实现：
因为此算法，操作对象是一个图，所以我们先来介绍一下图在JAVA代码中的储存方式：
好了，开始切入正题。
在视频中，运用到了两个矩阵，一个是用来存路径长度的，一个使用来存路径的。
所以我们在定义函数参数时，也要定义两个二维数组：
在视频中，Up主先对这两个矩阵进行了初始化：
D矩阵是放路径长度的（也就是权值）-->这些信息从已经构造好的图里面获取：
而在代码中，就是从这个矩阵获取：
而Path矩阵的初始化，只需要按照D矩阵进行初始化即可。
接下来我们在代码中，去初始化这两个数组：
接下来，需要创建n个中间结点，从0开始，n是顶点的数量，所以定义一个循环：
在这个循环体中，我们要一直执行一下操作：
通过旧的D矩阵，也就是代码中的dist二维数组，创建一个新的矩阵D。
然后依据新的矩阵D，也就是新的dist二维数组，
以及旧的Path矩阵（也就代码中的pPath二维数组）
创建一个新的矩阵Path（也就是新的pPath二维数组）。
循环已结束，那么dist二维数组，存的就是一个顶点到另一个顶点的的总长度了。
pPaht二维数组，就存着具体的路径了。
代码实现：
注意：
已知Path矩阵，求多源最短路径：
每一行的储存思路，和并查集寻找根结点的方式是一样的，最终逆置顶点顺序即可。
算法源码：
/*** 佛洛依德算法* @param pPath 存最短路径* @param dist 放边的长度* */public void floydWarShall(int[][] dist,int[][] pPath){int n=arrayV.length;//获得顶点个数for (int i = 0; i <n ; i++) {Arrays.fill(dist[i],Integer.MAX_VALUE);//路径长度默认初始化成无穷大Arrays.fill(pPath,-1);//路径默认初始化成-1（无效值）}//接下来把matrix中的权重，赋值给dist二维数组，同时更行pPath/*** matrix这个二维数组，储存每一条边的权重* 如果matrix[i][j]==Integer.MAX_VALUE，那么说明i顶点到j顶点没有边*/for (int i = 0; i < n; i++) {for (int j = 0; j <n ; j++) {if(matrix[i][j]!=Integer.MAX_VALUE){//有边进来dist[i][j]=matrix[i][j];pPath[i][j]=i;//记录上一个顶点的下标}}}/* 以上是初始化 */for (int k = 0; k <n ; k++) {//定义中间节点的循环//每次一个中间节点，遍历一次整个二维数组for (int i = 0; i <n ; i++) {for (int j = 0; j <n ; j++) {if(matrix[i][k]!=Integer.MAX_VALUE&&//从i到中间节点 要有边matrix[k][j]!=Integer.MAX_VALUE&&//从中间节点到目标结点j 要有边dist[i][k]+matrix[k][j]<dist[i][j]){//新的路径长度要小于原来的路径长度/*满足以上三个条件，才能更行dist*/dist[i][j]=dist[i][k]+matrix[k][j];//dist更新完，接着更新pPathpPath[i][j]=pPath[k][j];//注意不能pPath[i][j]=k 这也是up强调的，不能直接赋值中间节点//因为如果i->k->j，此时是k//但是 i->t->k k->d->j 这种情况就不是了}}}}}