Java如何利用Dijkstra和Floyd分别求取图的最短路径(dijkstra,floyd,java,开发技术)

1 最短路径的概述

在生活中，图形结构的应用是最广泛的。比如常见的交通路线选择，站点可以看作顶点，站点之间如果有路径，则算作两点之间的边或者弧，站点之间的通行时间，可以看作边或者弧的权值。

上图就是生活中出行路线的选择映射到图形结构的案例。顶点作为站点，站点之间能够到达则拥有边，站点的之间的通行时间则是边的权值。

对于出行路线的选择，不同的人有不同的选择。其中有一种很常见的选择是要求出发地和目的地之间的总通行时间最短，而不在乎中途到底有几站。毕竟通行时间对于很多人来说是宝贵的！

这样的问题转转换为数学模型，就是求带权图的最短路径，就是求带权图形两顶点之间的权值最小的路径。即如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小。

实际上最短路径有两重含义，一个两顶点之间的路径数量最少，另一个是两顶点之间的路径距离最短，本次主要解决路径距离最短的问题，即最小权值和。常见的解决算法一般是两种，迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd)算法。

2 杰斯特拉（Dijkstra）算法

2.1 原理

迪杰斯特拉（Dijkstra）算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是寻找给定的加权图中指定顶点间最短路径问题的算法

Dijkstra算法并不是一下子就求出了起点到终点的最短路径，而是采用的是贪心算法策略，一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到起点和终点的最短路径。

通用步骤如下：

1.指定两个集合S和U。S的作用是记录已求出最短路径的顶点，而U则是记录还未求出最短路径的顶点，以及这些顶点到起始顶点的权。

2.指定一个起始顶点A，存入集合S中，其他顶点以及到顶点A的权存入集合U中，从U中找出并移除路径最短的顶点B，并将其加入到S中，并且更新U中对应的路径权值（更新源点将新加入节点作为中间节点到达其它节点的距离）；重复该操作直到遍历所有顶点，此时S中的集合就是起点A到其他各个顶点的最短路径。

迪杰斯特拉算法只支持非负权图，它计算的是单源最短路径，即单个源点到剩余节点的最短路径，时间复杂度为O(n²)，对稀疏图运行更快。如果想知道所有顶点到所有顶点的最短路径，那么等于在原有算法的基础上，再来一次循环，此时整个算法的时间复杂度就成了O(n³)。

2.2 案例分析

该案例对应着下面实现代码中的案例，设起始点为A，初始化A到其他点的路径数组{0, 99, 8, 2, 99, 3, 99}，初始化标志位数组{true, false, false, false, false, false, false}。

开始第一轮循环，排除已找到的路径，即排除0，寻找到A的最短路径，找到了A-D，即索引为3的顶点,设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的D可达的顶点路径到A点的最短路径，如果经过D点的路径比数组中已存在的最短路径小，那么更新值。

这里D点可达C、B，D-C+A-D=7<8，因此更新A-C的最短路径为7；D-B+A-D=11<99，因此更新A-B的最短路径为11，第一轮循环结束，此时最短路径数组为{0, 11, 7, 2, 99, 3, 99}，标志位数组为{true, false, false, true, false, false, false}:

开始第二轮循环，排除已找到的路径，即排除0、2，寻找到A的最短路径，这里找到3，即索引为5的顶点，即A-F，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的F可达的顶点路径到A点的最短路径，如果经过F点的路径比数组中已存在的最短路径小，那么更新值。

这里F点可达G，F-G+A-F=12<99，因此更新A-G的最短路径为12，第二轮循环结束，此时最短路径数组为{0, 11, 7, 2, 99, 3, 12}，标志位数组为{true, false, false, true, false, true, false}。

开始第三轮循环，排除已找到的路径，即排除0、2、3，寻找到A的最短路径，这里找到7，即索引为2的顶点，即A-C，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的C可达的顶点路径到A点的最短路径，如果经过C点的路径比数组中已存在的最短路径小，那么更新值。

这里C点可达B，C-B+A-C=11 = 11，因此不更新A-B的最短路径，第三轮循环结束，此时最短路径数组为{0, 11, 7, 2, 99, 3, 12}，标志位数组为{true, false, true, true, false, true, false}。

开始第四轮循环，排除已找到的路径，即排除0、2、3、7，寻找到A的最短路径，这里找到11，即索引为1的顶点，即A-B，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的B可达的顶点路径到A点的最短路径，如果经过B点的路径比数组中已存在的最短路径小，那么更新值。

这里B点可达E，B-E+A-B=18 < 99，因此更新A-E的最短路径为18，第四轮循环结束，此时最短路径数组为{0, 11, 7, 2, 18, 3, 12}，标志位数组为{true, true, true, true, false, true, false}。

开始第五轮循环，排除已找到的路径，即排除0、2、3、7、11，寻找到A的最短路径，这里找到12，即索引为6的顶点，即A-G，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的G可达的顶点路径到A点的最短路径，如果经过G点的路径比数组中已存在的最短路径小，那么更新值。

排除已找到的顶点，这里G点可达E，G-E+A-G=18 = 18，因此不更新最短路径，第五轮循环结束，此时最短路径数组为{0, 11, 7, 2, 18, 3, 12}，标志位数组为{true, true, true, true, false, true, true}。

开始第六轮循环，排除已找到的路径，即排除0、2、3、7、11、12，寻找到A的最短路径，这里找到18，即索引为4的顶点，即A-E，设置对应位置的最短路径标志位为true，更新未获取最短路径的顶点的最短路径，因为其他已找到的顶点的最短路径已经找到了，这里只需要更新新找到的E可达的顶点路径到A点的最短路径，如果经过E点的路径比数组中已存在的最短路径小，那么更新值。

排除已找到的顶点，这里不更新最短路径，第四轮循环结束，此时最短路径数组为{0, 11, 7, 2, 18, 3, 12}，标志位数组为{true, true, true, true, true, true, true}。

此时大循环结束，Dijkstra算法结束，顶点A到各个顶点的最短路径已经找到，即A到{A,B,C,D,E,F,G}的最短路径为{0, 11, 7, 2, 18, 3, 12}。

3 弗洛伊德（Floyd）算法

3.1 原理

弗洛伊德（Floyd）算法又称插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。算出来的结果是所有的节点到其余各节点之间的最短距离。

通用步骤如下：

1.设图顶点数为N。首先需要准备一个长度为N的距离矩阵S，矩阵S中的元素a[i][j]=sum的表示顶点i到顶点j的最短路径为sum；

2.然后对S矩阵进行初始化，距离矩阵S中顶点a[i][j]的值为顶点i到顶点j的直接权值；

3.然后对S矩阵循环进行N次更新，在第k次更新时，如果S矩阵的a[i][j] > a[i][k]+a[k][j]，那么更新a[i][j]=a[i][k]+a[k][j]。循环更新完毕，则算法完成，所有的节点到其余各节点之间的最短距离已经找到了。

相比于Dijkstra 算法，Floyd算法支持带有负权边的图，但是不能解决带有“负权回路”（或者叫“负权环”）的图，实际上如果一个图中带有“负权回路”那么这个图则没有最短路径。

Floyd算法的时间复杂度同样是时间复杂度O(n&sup3;)，空间复杂度是O(n&sup2;)，代码非常简单，但是思想相却是非常的巧妙，将所有的可能都枚举出来一一对比，取最小值，这样最终会得到最小值。

3.2 案例分析

该案例对应着下面实现代码中的案例：

首先初始化距离矩阵S如下：

然后就是三层嵌套循环，开始第一轮大循环，即当k=0，循环遍历S矩阵，判断是否小于 shortestPath[i][j]，即所有的路径都经过A点中转，如果经过A中转后的路径shortestPath[i][0] + shortestPath[k][0]< shortestPath[i][j]，自然更新路径：shortestPath[i][j]= shortestPath[i][0] + shortestPath[k][0]。一轮大循环之后的数组如下：

然后经过一共经过N次的大循环，表示经过所有的顶点，最终取得的矩阵如下：

4 邻接矩阵加权图实现

这里的实现能够构造一个基于邻接矩阵实现无向加权图的类，并且提供深度优先遍历和广度优先遍历的方法，提供获取边集数组的方法，提供Prim和Kruskal两种求最小生成树的方法，提供Dijkstra和Floyd两种求最短路径的方法。

/***无向加权图邻接矩阵实现*{@linkMatrixDijkstraAndFloyd#MatrixDijkstraAndFloyd(Object[],Edge[])}构建无向加权图*{@linkMatrixDijkstraAndFloyd#DFS()}深度优先遍历无向加权图*{@linkMatrixDijkstraAndFloyd#BFS()}广度优先遍历无向加权图*{@linkMatrixDijkstraAndFloyd#toString()}输出无向加权图*{@linkMatrixDijkstraAndFloyd#prim()}Prim算法实现最小生成树*{@linkMatrixDijkstraAndFloyd#kruskal()}Kruskal算法实现最小生成树*{@linkMatrixDijkstraAndFloyd#kruskalAndPrim()}Kruskal算法结合Prim算法实现最小生成树*{@linkMatrixDijkstraAndFloyd#getEdges()}获取边集数组*{@linkMatrixDijkstraAndFloyd#dijkstra(int)}()}Dijkstra算法获取指定顶点到所有顶点的最短路径*{@linkMatrixDijkstraAndFloyd#dijkstra(int,int)}Dijkstra算法获取指定顶点到指定顶点的最短路径*{@linkMatrixDijkstraAndFloyd#floyd()}Floyd获取所有顶点到所有顶点的最短路径**@authorlx*/publicclassMatrixDijkstraAndFloyd<E>{/***顶点数组*/privateObject[]vertexs;/***邻接矩阵*/privateint[][]matrix;/****/privateEdge<E>[]edges;/***由于是加权图,这里设置一个边的权值上限,任何边的最大权值不能大于等于该值，在实际应用中，该值应该根据实际情况确定*/privatestaticfinalintNO_EDGE=99;/***边对象,具有权值,在构建加权无向图时使用*/privatestaticclassEdge<E>{privateEfrom;privateEto;privateintweight;publicEdge(Efrom,Eto,intweight){this.from=from;this.to=to;this.weight=weight;}@OverridepublicStringtoString(){return"Edge{"+"from="+from+",to="+to+",weight="+weight+'}';}}/***创建无向加权图**@paramvertexs顶点数组*@paramedges边对象数组*/publicMatrixDijkstraAndFloyd(Object[]vertexs,Edge<E>[]edges){//初始化边数组this.edges=edges;//初始化顶点数组,并添加顶点this.vertexs=Arrays.copyOf(vertexs,vertexs.length);//初始化边矩阵,并预先填充边信息this.matrix=newint[vertexs.length][vertexs.length];for(inti=0;i<vertexs.length;i++){for(intj=0;j<vertexs.length;j++){if(i==j){this.matrix[i][j]=0;}else{this.matrix[i][j]=NO_EDGE;}}}for(Edge<E>edge:edges){//读取一条边的起始顶点和结束顶点索引值intp1=getPosition(edge.from);intp2=getPosition(edge.to);//对称的两个点位都置为edge.weight,无向图可以看作相互可达的有向图this.matrix[p1][p2]=edge.weight;this.matrix[p2][p1]=edge.weight;}}/***获取某条边的某个顶点所在顶点数组的索引位置**@parame顶点的值*@return所在顶点数组的索引位置,或者-1-表示不存在*/privateintgetPosition(Ee){for(inti=0;i<vertexs.length;i++){if(vertexs[i]==e){returni;}}return-1;}/***深度优先搜索遍历图,类似于树的前序遍历,*/publicvoidDFS(){//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点boolean[]visited=newboolean[vertexs.length];//初始化所有顶点都没有被访问for(inti=0;i<vertexs.length;i++){visited[i]=false;}System.out.println("DFS:");System.out.print("\t");for(inti=0;i<vertexs.length;i++){if(!visited[i]){DFS(i,visited);}}System.out.println();}/***深度优先搜索遍历图的递归实现,类似于树的先序遍历*因此模仿树的先序遍历,同样借用栈结构,这里使用的是方法的递归,隐式的借用栈**@parami顶点索引*@paramvisited访问标志数组*/privatevoidDFS(inti,boolean[]visited){visited[i]=true;System.out.print(vertexs[i]+"");//遍历该顶点的所有邻接点。若该邻接点是没有访问过，那么继续递归遍历领接点for(intw=firstVertex(i);w>=0;w=nextVertex(i,w)){if(!visited[w]){DFS(w,visited);}}}/***广度优先搜索图,类似于树的层序遍历*因此模仿树的层序遍历,同样借用队列结构*/publicvoidBFS(){//辅组队列Queue<Integer>indexLinkedList=newLinkedList<>();//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点boolean[]visited=newboolean[vertexs.length];for(inti=0;i<vertexs.length;i++){visited[i]=false;}System.out.println("BFS:");System.out.print("\t");for(inti=0;i<vertexs.length;i++){if(!visited[i]){visited[i]=true;System.out.print(vertexs[i]+"");indexLinkedList.add(i);}if(!indexLinkedList.isEmpty()){//j索引出队列Integerj=indexLinkedList.poll();//继续访问j的邻接点for(intk=firstVertex(j);k>=0;k=nextVertex(j,k)){if(!visited[k]){visited[k]=true;System.out.print(vertexs[k]+"");//继续入队列indexLinkedList.add(k);}}}}System.out.println();}/***返回顶点v的第一个邻接顶点的索引，失败则返回-1**@paramv顶点v在数组中的索引*@return返回顶点v的第一个邻接顶点的索引，失败则返回-1*/privateintfirstVertex(intv){//如果索引超出范围,则返回-1if(v<0||v>(vertexs.length-1)){return-1;}/*根据邻接矩阵的规律:顶点索引v对应着边二维矩阵的matrix[v][i]一行记录*从i=0开始*/for(inti=0;i<vertexs.length;i++){if(matrix[v][i]!=0&&matrix[v][i]!=NO_EDGE){returni;}}return-1;}/***返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1**@paramv顶点索引*@paramw第一个邻接点索引*@return返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1*/privateintnextVertex(intv,intw){//如果索引超出范围,则返回-1if(v<0||v>(vertexs.length-1)||w<0||w>(vertexs.length-1)){return-1;}/*根据邻接矩阵的规律:顶点索引v对应着边二维矩阵的matrix[v][i]一行记录*由于邻接点w的索引已经获取了,所以从i=w+1开始寻找*/for(inti=w+1;i<vertexs.length;i++){if(matrix[v][i]!=0&&matrix[v][i]!=NO_EDGE){returni;}}return-1;}/***输出图**@return输出图字符串*/@OverridepublicStringtoString(){StringBuilderstringBuilder=newStringBuilder();for(inti=0;i<vertexs.length;i++){for(intj=0;j<vertexs.length;j++){stringBuilder.append(matrix[i][j]).append("\t");}stringBuilder.append("\n");}returnstringBuilder.toString();}/***Prim算法求最小生成树*/publicvoidprim(){System.out.println("prim:");//对应节点应该被连接的前驱节点,用来输出//默认为0,即前驱结点为第一个节点int[]mid=newint[matrix.length];//如果某顶点作为末端顶点被连接，对应位置应该为true//第一个顶点默认被连接boolean[]connected=newboolean[matrix.length];connected[0]=true;//存储未连接顶点到已连接顶点的最短距离(最小权)int[]dis=newint[matrix.length];//首先将矩阵第一行即其他顶点到0索引顶点的权值拷贝进去System.arraycopy(matrix[0],0,dis,0,matrix.length);//存储路径长度intsum=0;//最小权值intmin;/*默认第一个顶点已经找到了,因此最多还要需要大循环n-1次*/for(intk=1;k<matrix.length;k++){min=NO_EDGE;//最小权值的顶点的索引intminIndex=0;/*寻找权值最小的且未被连接的顶点索引*/for(inti=1;i<matrix.length;i++){//排除已连接的顶点,排除权值等于0的值,这里权值等于0表示已生成的最小生成树的顶点都未能与该顶点连接if(!connected[i]&&dis[i]!=0&&dis[i]<min){min=dis[i];minIndex=i;}}//如果没找到,那么该图可能不是连通图,直接返回了,此时最小生成树没啥意义if(minIndex==0){return;}//权值和增加sum+=min;//该新连接顶点对应的索引值变成true,表示已被连接,后续判断时跳过该顶点connected[minIndex]=true;//输出对应的前驱顶点到该最小顶点的权值System.out.println("\t"+vertexs[mid[minIndex]]+"--->"+vertexs[minIndex]+"权值:"+min);/*在新顶点minIndex加入之前的其他所有顶点到连接顶点最小的权值已经计算过了因此只需要更新其他未连接顶点到新连接顶点minIndex是否还有更短的权值,有的话就更新找到距离已连接的顶点权最小的顶点*/for(inti=1;i<matrix.length;i++){//如果该顶点未连接if(!connected[i]){/*如果新顶点到未连接顶点i的权值不为0,并且比原始顶点到未连接顶点i的权值还要小,那么更新对应位置的最小权值*/if(matrix[minIndex][i]!=0&&dis[i]>matrix[minIndex][i]){//更新最小权值dis[i]=matrix[minIndex][i];//更新前驱节点索引为新加入节点索引mid[i]=minIndex;}}}}System.out.println("\t"+"sum:"+sum);}/***Kruskal算法求最小生成树传统实现,要求知道边集数组,和顶点数组*/publicvoidkruskal(){System.out.println("Kruskal:");//由于创建图的时候保存了边集数组,这里直接使用就行了//Edge[]edges=getEdges();//this.edges=edges;//对边集数组进行排序Arrays.sort(this.edges,Comparator.comparingInt(o->o.weight));//用于保存已有最小生成树中每个顶点在该最小树中的最终终点的索引int[]vends=newint[this.edges.length];//能够知道终点索引范围是[0,this.edges.length-1],因此填充edges.length表示没有终点Arrays.fill(vends,this.edges.length);intsum=0;for(Edge<E>edge:this.edges){//获取第i条边的起点索引fromintfrom=getPosition(edge.from);//获取第i条边的终点索引tointto=getPosition(edge.to);//获取顶点from在"已有的最小生成树"中的终点intm=getEndIndex(vends,from);//获取顶点to在"已有的最小生成树"中的终点intn=getEndIndex(vends,to);//如果m!=n，意味着没有形成环路,则可以添加,否则直接跳过,进行下一条边的判断if(m!=n){//添加设置原始终点索引m在已有的最小生成树中的终点为nvends[m]=n;System.out.println("\t"+vertexs[from]+"--->"+vertexs[to]+"权值:"+edge.weight);sum+=edge.weight;}}System.out.println("\t"+"sum:"+sum);//System.out.println(Arrays.toString(this.edges));}/***获取顶点索引i的终点如果没有终点则返回顶点索引本身**@paramvends顶点在最小生成树中的终点*@parami顶点索引*@return顶点索引i的终点如果没有终点则返回顶点索引本身*/privateintgetEndIndex(int[]vends,inti){//这里使用循环查找的逻辑,寻找的是最终的终点while(vends[i]!=this.edges.length){i=vends[i];}returni;}/***如果没有现成的边集数组，那么根据邻接矩阵结构获取图中的边集数组**@return图的边集数组*/privateEdge[]getEdges(){List<Edge>edges=newArrayList<>();/*遍历矩阵数组只需要遍历一半就行了*/for(inti=0;i<vertexs.length;i++){for(intj=i+1;j<vertexs.length;j++){//如果存在边if(matrix[i][j]!=NO_EDGE&&matrix[i][j]!=0){edges.add(newEdge<>(vertexs[i],vertexs[j],matrix[i][j]));//edges[index++]=newEdge(vertexs[i],vertexs[j],matrix[i][j]);}}}returnedges.toArray(newEdge[0]);}/***Kruskal结合Prim算法.不需要知道边集,只需要矩阵数组,和顶点数组*同样是求最小权值的边,但是有一个默认起点顶点,该起点可以是要求[0,顶点数量-1]之间的任意值，同时查找最小权的边。*可能会有Bug,目前未发现*/publicvoidkruskalAndPrim(){System.out.println("kruskalAndPrim:");//已经找到的边携带的顶点对应的索引将变为true,其余未找到边对应的顶点将是falseboolean[]connected=newboolean[matrix.length];//这里选择第一个顶点为起点,表示以该顶点开始寻找包含该顶点的最小边connected[0]=true;intsum=0,n1=0,n2=0;//最小权值intmin;while(true){min=NO_EDGE;/*找出所有带有已找到顶点的边中,最小权值的边,只需要寻找对称矩阵的一半即可*///第一维for(inti=0;i<matrix.length;i++){//第二维for(intj=i+1;j<matrix.length;j++){//排除等于0的,排除两个顶点都找到了的,这里实际上已经隐含了排除环的逻辑,如果某条边的两个顶点都找到了,那么如果算上该条边,肯定会形成环//寻找剩下的最小的权值的边if(matrix[i][j]!=0&&connected[i]!=connected[j]&&matrix[i][j]<min){min=matrix[i][j];n1=i;n2=j;}}}//如果没找到最小权值,该图可能不是连通图,或者已经寻找完毕,直接返回if(min==NO_EDGE){System.out.println("\t"+"sum:"+sum);return;}//已经找到的边对应的两个顶点都置为trueconnected[n1]=true;connected[n2]=true;//输出找到的边和最小权值System.out.println("\t"+vertexs[n1]+"--->"+vertexs[n2]+"权值:"+min);sum+=min;}}/***Dijkstra算法求最短路径。**@paramstart起始顶点索引。即计算"顶点vs"到其它顶点的最短路径。*/publicvoiddijkstra(intstart){checkIndex(start);int[]shortestPathance=getShortestDistance(start,vertexs.length);//打印Dijkstra最短路径的结果System.out.println("Dijkstra("+vertexs[start]+"):");for(inti=0;i<vertexs.length;i++){System.out.println("\t("+vertexs[start]+"--->"+vertexs[i]+")最短路径:"+shortestPathance[i]);}}/***Dijkstra算法求最短路径**@paramstart起始点*@paramend终点,如果end=vertexs.length说明是遍历查找所有的最短路径*@return起始顶点到其他点或者指定点的最短权值*/privateint[]getShortestDistance(intstart,intend){/*1、该数组存放起始顶点到其他点的权值*/int[]shortestPathance=newint[vertexs.length];//初始化数据//首先设置起始点到顶点i到的最短路径为起始点到顶点i的权。System.arraycopy(matrix[start],0,shortestPathance,0,matrix.length);/*2、标志位数组.某个位置如果为true表示对应位置的顶点到起始顶点的最短路径已成功获取。*/boolean[]shortest=newboolean[vertexs.length];//首先设置起始点到自己的的路径已经找到了,为0shortest[start]=true;/*3、最多遍历vertexs.length-1次；每次找出起始点到一个顶点的最短路径。*/intk;intmin;for(inti=1;i<vertexs.length;i++){k=0;//寻找当前最小的路径；min=NO_EDGE;for(intj=0;j<vertexs.length;j++){//排除已经找到的最短路径之后，找到离start最近的顶点(k)。if(!shortest[j]&&shortestPathance[j]<min){min=shortestPathance[j];k=j;}}//先设置起始点到新顶点k的最短路径已经找到shortest[k]=true;if(end!=vertexs.length&&k==end){break;}//更新未获取最短路径的顶点的最短路径,因为其他已找到的顶点的最短路径已经找到了,这里指需要更新新加入的已找到的可达顶点的路径.for(intj=0;j<vertexs.length;j++){inttmp=matrix[k][j];//排除已经找到的最短路径，排除未连接的路径，排除等于0的路径（连接自己）之后//找到离start最如果新的最短路径比以前的最短路径还要短，则更新最短路径。if(!shortest[j]&&tmp!=NO_EDGE&&tmp!=0&&((tmp=min+tmp)<shortestPathance[j])){shortestPathance[j]=tmp;}}}returnshortestPathance;}/***索引检查**@paramindex多个索引*/privatevoidcheckIndex(int...index){for(inti:index){if(i<0||i>=vertexs.length){thrownewArrayIndexOutOfBoundsException("索引越界:"+i);}}}/***Dijkstra算法求最短路径。**@paramstart起始顶点索引。*@paramend结束点索引*/publicvoiddijkstra(intstart,intend){checkIndex(start,end);int[]shortestPathance=getShortestDistance(start,end);//打印Dijkstra最短路径的结果System.out.println("Dijkstra("+vertexs[start]+"--->"+vertexs[end]+")最短路径:"+shortestPathance[end]);}/***Floyd算法获取所有顶点到所有顶点的最短路径,代码很简单,思想很巧妙*/publicvoidfloyd(){//路径矩阵(两顶点最短路径,即最小权值)int[][]shortestPath=newint[matrix.length][matrix.length];/*初始化数据*/for(inti=0;i<matrix.length;i++){System.arraycopy(matrix[i],0,shortestPath[i],0,vertexs.length);}//计算最短路径for(intk=0;k<matrix.length;k++){for(inti=0;i<matrix.length;i++){for(intj=0;j<matrix.length;j++){//要求经过下标k顶点的两个路径都不能等于NO_EDGE,否则就是没有路径,NO_EDGE应该选取的足够的大,否则可能出错inttmp=(shortestPath[i][k]==NO_EDGE||shortestPath[k][j]==NO_EDGE)?NO_EDGE:(shortestPath[i][k]+shortestPath[k][j]);//如果经过下标为k顶点路径比原两点间路径更短，则更新shortestPath[i][j]if(shortestPath[i][j]>tmp){//i到j最短路径对应的值设为经过k的更小的一个shortestPath[i][j]=tmp;}}}}/*输出路径矩阵*/System.out.println("Floyd:");for(inti=0;i<matrix.length;i++){for(intj=0;j<matrix.length;j++){System.out.print("\t"+shortestPath[i][j]);}System.out.println();}}publicstaticvoidmain(String[]args){//顶点数组Character[]vexs={'A','B','C','D','E','F','G'};//边数组,加权值Edge[]edges={newEdge<>('A','C',8),newEdge<>('D','A',2),newEdge<>('A','F',3),newEdge<>('B','C',4),newEdge<>('C','D',5),newEdge<>('E','G',6),newEdge<>('E','B',7),newEdge<>('D','B',9),newEdge<>('F','G',9)};//构建图MatrixDijkstraAndFloyd<Character>matrixDijkstraAndFloyd=newMatrixDijkstraAndFloyd<Character>(vexs,edges);//输出图System.out.println(matrixDijkstraAndFloyd);//深度优先遍历matrixDijkstraAndFloyd.DFS();//广度优先遍历matrixDijkstraAndFloyd.BFS();//Prim算法输出最小生成树matrixDijkstraAndFloyd.prim();//Kruskal算法输出最小生成树matrixDijkstraAndFloyd.kruskal();//Kruskal算法结合Prim算法输出最小生成树,可能会有Bug,目前未发现matrixDijkstraAndFloyd.kruskalAndPrim();//Dijkstra算法获取某个索引的顶点到其它各个顶点的最短距离//这里参数是索引,也可以是一个顶点,需要稍微修改代码获取顶点的索引,比较简单这里就不做了matrixDijkstraAndFloyd.dijkstra(0);//Dijkstra算法获取一个顶点到另一个顶点的最短距离matrixDijkstraAndFloyd.dijkstra(2,0);//Floyd算法获取所有顶点到所有顶点的最短路径matrixDijkstraAndFloyd.floyd();}}

5 邻接表加权图实现

这里的实现能够构造一个基于邻接表实现无向加权图的类；并且提供深度优先遍历和广度优先遍历的方法，提供获取边集数组的方法，提供Prim和Kruskal两种求最小生成树的方法，提供Dijkstra和Floyd两种求最短路径的方法。

/***无向加权图邻接表实现*{@linkListDijkstraAndFloyd#ListDijkstraAndFloyd(Object[],Edge[])}构建无向加权图*{@linkListDijkstraAndFloyd#DFS()}深度优先遍历无向加权图*{@linkListDijkstraAndFloyd#BFS()}广度优先遍历无向加权图*{@linkListDijkstraAndFloyd#toString()}输出无向加权图*{@linkListDijkstraAndFloyd#prim()}Prim算法实现最小生成树*{@linkListDijkstraAndFloyd#kruskal()}Kruskal算法实现最小生成树*{@linkListDijkstraAndFloyd#getEdges()}获取边集数组*{@linkListDijkstraAndFloyd#dijkstra(int)}()}获取指定顶点到所有顶点的最短路径*{@linkListDijkstraAndFloyd#dijkstra(int,int)}获取指定顶点到指定顶点的最短路径*{@linkListDijkstraAndFloyd#floyd()}Floyd获取所有顶点到所有顶点的最短路径**@authorlx*/publicclassListDijkstraAndFloyd<E>{/***顶点类**@param<E>*/privateclassNode<E>{/***顶点信息*/Edata;/***指向第一条依附该顶点的边*/LNodefirstLNode;publicNode(Edata,LNodefirstLNode){this.data=data;this.firstLNode=firstLNode;}}/***边表节点类*/privateclassLNode{/***该边所指向的顶点的索引位置*/intvertex;/***该边的权值*/intweight;/***指向下一条边的指针*/LNodenextLNode;}/***边对象,具有权值,在构建加权无向图时使用*/privatestaticclassEdge<E>{privateEfrom;privateEto;privateintweight;publicEdge(Efrom,Eto,intweight){this.from=from;this.to=to;this.weight=weight;}@OverridepublicStringtoString(){return"Edge{"+"from="+from+",to="+to+",weight="+weight+'}';}}/***顶点数组*/privateNode<E>[]vertexs;/***边数组*/privateEdge<E>[]edges;/***由于是加权图,这里设置一个边的权值上限,任何边的最大权值不能大于等于该值，在实际应用中，该值应该根据实际情况确定*/privatestaticfinalintNO_EDGE=99;/***创建无向加权图**@paramvexs顶点数组*@paramedges边二维数组*/publicListDijkstraAndFloyd(E[]vexs,Edge<E>[]edges){this.edges=edges;/*初始化顶点数组,并添加顶点*/vertexs=newNode[vexs.length];for(inti=0;i<vertexs.length;i++){vertexs[i]=newNode<>(vexs[i],null);}/*初始化边表,并添加边节点到边表尾部,即采用尾插法*/for(Edge<E>edge:edges){//读取一条边的起始顶点和结束顶点索引值intp1=getPosition(edge.from);intp2=getPosition(edge.to);intweight=edge.weight;/*这里需要相互添加边节点,无向图可以看作相互可达的有向图*///初始化lnode1边节点LNodelnode1=newLNode();lnode1.vertex=p2;lnode1.weight=weight;//将LNode链接到"p1所在链表的末尾"if(vertexs[p1].firstLNode==null){vertexs[p1].firstLNode=lnode1;}else{linkLast(vertexs[p1].firstLNode,lnode1);}//初始化lnode2边节点LNodelnode2=newLNode();lnode2.vertex=p1;lnode2.weight=weight;//将lnode2链接到"p2所在链表的末尾"if(vertexs[p2].firstLNode==null){vertexs[p2].firstLNode=lnode2;}else{linkLast(vertexs[p2].firstLNode,lnode2);}}}/***获取某条边的某个顶点所在顶点数组的索引位置**@parame顶点的值*@return所在顶点数组的索引位置,或者-1-表示不存在*/privateintgetPosition(Ee){for(inti=0;i<vertexs.length;i++){if(vertexs[i].data==e){returni;}}return-1;}/***将lnode节点链接到边表的最后,采用尾插法**@paramfirst边表头结点*@paramnode将要添加的节点*/privatevoidlinkLast(LNodefirst,LNodenode){while(true){if(first.vertex==node.vertex){return;}if(first.nextLNode==null){break;}first=first.nextLNode;}first.nextLNode=node;}@OverridepublicStringtoString(){StringBuilderstringBuilder=newStringBuilder();for(inti=0;i<vertexs.length;i++){stringBuilder.append(i).append("(").append(vertexs[i].data).append("):");LNodenode=vertexs[i].firstLNode;while(node!=null){stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append("-").append(node.weight).append(")");node=node.nextLNode;if(node!=null){stringBuilder.append("->");}else{break;}}stringBuilder.append("\n");}returnstringBuilder.toString();}/***深度优先搜索遍历图的递归实现,类似于树的先序遍历*因此模仿树的先序遍历,同样借用栈结构,这里使用的是方法的递归,隐式的借用栈**@parami顶点索引*@paramvisited访问标志数组*/privatevoidDFS(inti,boolean[]visited){//索引索引标记为true,表示已经访问了visited[i]=true;System.out.print(vertexs[i].data+"");//获取该顶点的边表头结点LNodenode=vertexs[i].firstLNode;//循环遍历该顶点的邻接点,采用同样的方式递归搜索while(node!=null){if(!visited[node.vertex]){DFS(node.vertex,visited);}node=node.nextLNode;}}/***深度优先搜索遍历图,类似于树的前序遍历,*/publicvoidDFS(){//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点boolean[]visited=newboolean[vertexs.length];//初始化所有顶点都没有被访问for(inti=0;i<vertexs.length;i++){visited[i]=false;}System.out.println("DFS:");System.out.print("\t");/*循环搜索*/for(inti=0;i<vertexs.length;i++){//如果对应索引的顶点的访问标记为false,则搜索该顶点if(!visited[i]){DFS(i,visited);}}/*走到这一步,说明顶点访问标记数组全部为true,说明全部都访问到了,深度搜索结束*/System.out.println();}/***广度优先搜索图,类似于树的层序遍历*因此模仿树的层序遍历,同样借用队列结构*/publicvoidBFS(){//辅组队列Queue<Integer>indexLinkedList=newLinkedList<>();//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点boolean[]visited=newboolean[vertexs.length];//初始化所有顶点都没有被访问for(inti=0;i<vertexs.length;i++){visited[i]=false;}System.out.println("BFS:");System.out.print("\t");for(inti=0;i<vertexs.length;i++){//如果访问方剂为false,则设置为true,表示已经访问,然后开始访问if(!visited[i]){visited[i]=true;System.out.print(vertexs[i].data+"");indexLinkedList.add(i);}//判断队列是否有值,有就开始遍历if(!indexLinkedList.isEmpty()){//出队列Integerj=indexLinkedList.poll();LNodenode=vertexs[j].firstLNode;while(node!=null){intk=node.vertex;if(!visited[k]){visited[k]=true;System.out.print(vertexs[k].data+"");//继续入队列indexLinkedList.add(k);}node=node.nextLNode;}}}System.out.println();}/***Prim算法求最小生成树*/publicvoidprim(){System.out.println("prim:");//对应节点应该被连接的前驱节点,用来输出//默认为0,即前驱结点为第一个节点int[]mid=newint[vertexs.length];intstart=0;intmin,tmp,sum=0;intnum=vertexs.length;//顶点间边的权值//存储未连接顶点到已连接顶点的最短距离(最小权)int[]dis=newint[num];//初始化"顶点的权值数组"，//将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。//首先将其他顶点到0索引顶点的权值存储进去for(inti=0;i<num;i++){dis[i]=getWeight(start,i);}//如果某顶点作为末端顶点被连接，对应位置应该为true//第一个顶点默认被连接boolean[]connected=newboolean[vertexs.length];connected[0]=true;/*默认第一个顶点已经找到了,因此最多还要需要大循环n-1次*/for(intk=1;k<num;k++){min=NO_EDGE;//最小权值的顶点的索引intminIndex=0;//在未被加入到最小生成树的顶点中，找出权值最小的顶点。for(inti=1;i<vertexs.length;i++){//排除已连接的顶点,排除权值等于0的值,因为这里默认顶点指向自己的权值为0if(!connected[i]&&dis[i]!=0&&dis[i]<min){min=dis[i];minIndex=i;}}//如果没找到,那么该图可能不是连通图,直接返回了,此时最小生成树没啥意义if(minIndex==0){return;}//权值和增加sum+=min;//该新连接顶点对应的索引值变成true,表示已被连接,后续判断时跳过该顶点connected[minIndex]=true;//输出对应的前驱顶点到该最小顶点的权值System.out.println("\t"+vertexs[mid[minIndex]].data+"--->"+vertexs[minIndex].data+"权值:"+min);/*在新顶点minIndex加入之前的其他所有顶点到连接顶点最小的权值已经计算过了因此只需要更新其他顶点到新连接顶点minIndex是否还有更短的权值,有的话就更新找到距离已连接的顶点权最小的顶点*/for(inti=1;i<num;i++){//如果该顶点未连接if(!connected[i]){//获取minindex顶点到未连接顶点i的权值tmp=getWeight(minIndex,i);/*如果新顶点到未连接顶点i的权值不为0,并且比原始顶点到未连接顶点i的权值还要小,那么更新对应位置的最小权值*/if(tmp!=0&&dis[i]>tmp){dis[i]=tmp;//更新前驱节点索引为新加入节点索引mid[i]=minIndex;}}}}System.out.println("\t"+"sum:"+sum);}/***尝试获取边起点start到边终点end的边的权值,当然可能获取不到**@paramstart边起点*@paramend边终点*@return返回权值;如果起点和终点相同则返回0;如果边起点和边终点之间并没有边,则返回NO_EDGE*/privateintgetWeight(intstart,intend){//如果start=end，则返回0if(start==end){return0;}//获取该顶点的边表的第一个值LNodenode=vertexs[start].firstLNode;//循环查找边表,看能否找到对应的索引=end,找不到就返回NO_EDGE,表示两个顶点未连接。while(node!=null){if(end==node.vertex){returnnode.weight;}node=node.nextLNode;}returnNO_EDGE;}/***Kruskal算法求最小生成树,可以说邻接矩阵和邻接链表的实现方式是完全一致的*/publicvoidkruskal(){System.out.println("Kruskal:");//由于创建图的时候保存了边集数组,这里直接使用就行了//Edge[]edges=getEdges();//this.edges=edges;//对边集数组进行排序Arrays.sort(this.edges,Comparator.comparingInt(o->o.weight));//用于保存已有最小生成树中每个顶点在该最小树中的最终终点的索引int[]vends=newint[this.edges.length];//能够知道终点索引范围是[0,this.edges.length-1],因此填充edges.length表示没有终点Arrays.fill(vends,this.edges.length);intsum=0;for(Edge<E>edge:this.edges){//获取第i条边的起点索引fromintfrom=getPosition(edge.from);//获取第i条边的终点索引tointto=getPosition(edge.to);//获取顶点from在"已有的最小生成树"中的终点intm=getEndIndex(vends,from);//获取顶点to在"已有的最小生成树"中的终点intn=getEndIndex(vends,to);//如果m!=n，意味着没有形成环路,则可以添加,否则直接跳过,进行下一条边的判断if(m!=n){//添加设置原始终点索引m在已有的最小生成树中的终点为nvends[m]=n;System.out.println("\t"+vertexs[from].data+"--->"+vertexs[to].data+"权值:"+edge.weight);sum+=edge.weight;}}System.out.println("\t"+"sum:"+sum);//System.out.println(Arrays.toString(this.edges));}/***获取顶点索引i的终点如果没有终点则返回顶点索引本身**@paramvends顶点在最小生成树中的终点*@parami顶点索引*@return顶点索引i的终点如果没有终点则返回顶点索引本身*/privateintgetEndIndex(int[]vends,inti){//这里使用循环查找的逻辑,寻找的是最终的终点while(vends[i]!=this.edges.length){i=vends[i];}returni;}/***如果没有现成的边集数组，那么根据邻接表结构获取图中的边集数组**@return图的边集数组*/privateEdge[]getEdges(){List<Edge>edges=newArrayList<>();//遍历顶点数组for(inti=0;i<vertexs.length;i++){LNodenode=vertexs[i].firstLNode;while(node!=null){//只需添加起点索引小于终点索引的边就行了if(node.vertex>i){edges.add(newEdge<>(vertexs[i].data,vertexs[node.vertex].data,node.weight));}node=node.nextLNode;}}returnedges.toArray(newEdge[0]);}/***Dijkstra算法求最短路径。**@paramstart起始顶点索引。即计算"顶点vs"到其它顶点的最短路径。*/publicvoiddijkstra(intstart){checkIndex(start);int[]distance=getShortestDistance(start,vertexs.length);//打印dijkstra最短路径的结果System.out.println("dijkstra("+vertexs[start].data+"):");for(inti=0;i<vertexs.length;i++){System.out.println("\t("+vertexs[start].data+"--->"+vertexs[i].data+")最短路径:"+distance[i]);}}/***Dijkstra算法求最短路径。**@paramstart起始顶点索引。*@paramend结束点索引*/publicvoiddijkstra(intstart,intend){checkIndex(start,end);int[]shortestPathance=getShortestDistance(start,end);//打印dijkstra最短路径的结果System.out.println("Dijkstra("+vertexs[start].data+"--->"+vertexs[end].data+")最短路径:"+shortestPathance[end]);}/***Dijkstra算法求最短路径**@paramstart起始点*@paramend终点,如果end=vertexs.length说明是遍历查找所有的最短路径*@return起始顶点到其他点或者指定点的最短权值*/privateint[]getShortestDistance(intstart,intend){/*1、该数组存放起始顶点到其他点的权值*/int[]distance=newint[vertexs.length];//初始化数据for(inti=0;i<vertexs.length;i++){//首先设置起始点到顶点i到的最短路径为起始点到顶点i的权。distance[i]=getWeight(start,i);}/*2、标志位数组.某个位置表示true表示,对应位置的顶点到起始顶点的最短路径已成功获取。*/boolean[]shortest=newboolean[vertexs.length];//首先设置起始点到自己的的路径已经找到了,为0shortest[start]=true;/*3、最多遍历vertexs.length-1次；每次找出起始点到一个顶点的最短路径。*/intk;intmin;for(inti=1;i<vertexs.length;i++){k=0;//寻找当前最小的路径；min=NO_EDGE;for(intj=0;j<vertexs.length;j++){//排除已经找到的最短路径之后，找到离start最近的顶点(k)。if(!shortest[j]&&distance[j]<min){min=distance[j];k=j;}}//先设置起始点到新顶点k的最短路径已经找到shortest[k]=true;if(end!=vertexs.length&&k==end){break;}//更新未获取最短路径的顶点的最短路径,因为其他已找到的顶点的最短路径已经找到了,这里指需要更新新加入的已找到的可达顶点的路径.for(intj=0;j<vertexs.length;j++){inttmp=getWeight(k,j);//排除已经找到的最短路径，排除未连接的路径，排除等于0的路径（连接自己）之后//找到离start最如果新的最短路径比以前的最短路径还要短，则更新最短路径。if(!shortest[j]&&tmp!=NO_EDGE&&tmp!=0&&((tmp=min+tmp)<distance[j])){distance[j]=tmp;}}}returndistance;}/***索引检查**@paramindex多个索引*/privatevoidcheckIndex(int...index){for(inti:index){if(i<0||i>=vertexs.length){thrownewArrayIndexOutOfBoundsException("索引越界:"+i);}}}/***Floyd算法获取所有顶点到所有顶点的最短路径,与邻接矩阵的实现基本一致*/publicvoidfloyd(){//路径矩阵(两顶点最短路径,即最小权值)int[][]shortestPath=newint[vertexs.length][vertexs.length];/*初始化数据*/for(inti=0;i<vertexs.length;i++){for(intj=0;j<vertexs.length;j++){//获取两点的直接权值//如果是频繁调用该方法,因此可以创建一个属于对象的权值矩阵用来保存权值,这里为了简单没做shortestPath[i][j]=getWeight(i,j);}}//计算最短路径for(intk=0;k<vertexs.length;k++){for(inti=0;i<vertexs.length;i++){for(intj=0;j<vertexs.length;j++){//要求经过下标k顶点的两个路径都不能等于NO_EDGE,否则就是没有路径,NO_EDGE应该选取的足够的大,否则可能出错inttmp=(shortestPath[i][k]==NO_EDGE||shortestPath[k][j]==NO_EDGE)?NO_EDGE:(shortestPath[i][k]+shortestPath[k][j]);//如果经过下标为k顶点路径比原两点间路径更短，则更新shortestPath[i][j]if(shortestPath[i][j]>tmp){//i到j最短路径对应的值设为经过k的更小的一个shortestPath[i][j]=tmp;}}}}/*输出路径矩阵*/System.out.println("Floyd:");for(inti=0;i<vertexs.length;i++){for(intj=0;j<vertexs.length;j++){System.out.print("\t"+shortestPath[i][j]);}System.out.println();}}publicstaticvoidmain(String[]args){//顶点数组Character[]vexs={'A','B','C','D','E','F','G'};//边数组,加权值Edge[]edges={newEdge<>('A','C',8),newEdge<>('D','A',2),newEdge<>('A','F',3),newEdge<>('B','C',4),newEdge<>('C','D',5),newEdge<>('E','G',6),newEdge<>('E','B',7),newEdge<>('D','B',9),newEdge<>('F','G',9)};//构建图ListDijkstraAndFloyd<Character>listDijkstraAndFloyd=newListDijkstraAndFloyd<Character>(vexs,edges);//输出图System.out.println(listDijkstraAndFloyd);//深度优先遍历//DFS://ACBEGFDlistDijkstraAndFloyd.DFS();//广度优先遍历//BFS://ACDFBGElistDijkstraAndFloyd.BFS();//Prim算法求最小生成树listDijkstraAndFloyd.prim();//Kruskal算法求最小生成树listDijkstraAndFloyd.kruskal();//Dijkstra算法获取某个索引的顶点到其它各个顶点的最短距离//这里参数是索引,也可以是一个顶点,需要稍微修改代码获取顶点的索引,比较简单这里就不做了listDijkstraAndFloyd.dijkstra(0);//Dijkstra算法获取一个顶点到另一个顶点的最短距离listDijkstraAndFloyd.dijkstra(2,0);//Floyd算法获取所有顶点到所有顶点的最短路径listDijkstraAndFloyd.floyd();}}