最短路径[floyd算法]-----视频讲解+代码实现

求最短路径，一般有三种方法：

单源最短路径--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  这种情况就不是了}}}}}