参考资料：OI-wiki

发布时间：2025-06-24 17:10:21  作者：北方职教升学中心  阅读量：520

publicstaticvoidtestGraphBellmanFord(){Stringstr ="syztx";char[]array =str.toCharArray();GraphByMatrixg =newGraphByMatrix(str.length(),true);g.initArrayV(array);for(inti =0;i <str.length();i++){Arrays.fill(g.matrix[i],Integer.MAX_VALUE);}//负权回路实例//        g.addEdge('s', 't', 6);//        g.addEdge('s', 'y', 7);//        g.addEdge('y', 'z', 9);//        g.addEdge('y', 'x', -3);//        g.addEdge('y', 's', 1);//        g.addEdge('z', 's', 2);//        g.addEdge('z', 'x', 7);//        g.addEdge('t', 'x', 5);//        g.addEdge('t', 'y', -8);//        g.addEdge('t', 'z', -4);//        g.addEdge('x', 't', -2);//不存在负权回路的情况g.addEdge('s','t',6);g.addEdge('s','y',7);g.addEdge('y','z',9);g.addEdge('y','x',-3);g.addEdge('z','s',2);g.addEdge('z','x',7);g.addEdge('t','x',5);g.addEdge('t','y',8);g.addEdge('t','z',-4);g.addEdge('x','t',-2);int[]dist =newint[array.length];int[]parentPath =newint[array.length];booleanfig =g.bellmanFord('s',dist,parentPath);if(fig){g.printShortPath('s',dist,parentPath);}else{System.out.println("存在负权回路");}}

运行结果如下：

三、

• 时间复杂度：

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 + 1，而最短路的边数最多为 n - 1，因此整个算法最多执行 n - 1 轮松弛操作。

对那些刚刚加入 S 集合的结点的所有出边执行松弛操作。Floyd-Warshall 算法

• 算法概括：

Floyd-Warshall 算法是用来求任意两个结点之间的最短路的。

• 代码如下：

/**     *     * @param dist 存储各个顶点之间的最小权值     * @param pPath 存储各个顶点之间的最短权值路径     */publicvoidfloyWarShall(int[][]dist,int[][]pPath){//初始化for(inti =0;i <size;i++){Arrays.fill(dist[i],Integer.MAX_VALUE);Arrays.fill(pPath[i],-1);}//将边填入到 dist 数据，给后续动态规划初始化for(inti =0;i <size;i++){for(intj =0;j <size;j++){//存在边if(matrix[i][j]!=Integer.MAX_VALUE){dist[i][j]=matrix[i][j];pPath[i][j]=i;//边不存在的情况}else{pPath[i][j]=-1;}if(i ==j){dist[i][j]=0;pPath[i][j]=-1;}}}//动态规划for(intk =0;k <size;k++){for(inti =0;i <size;i++){for(intj =0;j <size;j++){if(dist[i][k]!=Integer.MAX_VALUE&&dist[k][j]!=Integer.MAX_VALUE&&dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];pPath[i][j]=pPath[k][j];}}}}//下面的代码为测试代码，打印 dist，和 pPathfor(inti =0;i <size;i++){for(intj =0;j <size;j++){if(dist[i][j]==Integer.MAX_VALUE){System.out.print(" * ");}else{System.out.print(dist[i][j]+" ");}}System.out.println();}System.out.println("=========打印路径==========");for(inti =0;i <size;i++){for(intj =0;j <size;j++){System.out.print(pPath[i][j]+" ");}System.out.println();}System.out.println("=================");}

• 测试 Floyd-Warshall 算法：

测试图例如下：

publicstaticvoidtestGraphFloydWarShall(){Stringstr ="12345";char[]array =str.toCharArray();GraphByMatrixg =newGraphByMatrix(str.length(),true);g.initArrayV(array);//没有边，设置为 最大值。故总时间复杂度为 O（n * m）。Dijkstra 算法
算法概括：
Dijkstra 是一种求解非负权图上单源最短路径的算法。
若最短路径经过 k，则 D(i,j,k) = D(i,k,k - 1) + D(k,j,k - 1)。
若最短路径不经过 k，则 D(i,j,k) = D(i,j,k - 1)。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。其中 n 为顶点个数，m 为 边的个数。
publicvoidprintShortPath(charvSrc,int[]dist,int[]pPath){intsrcIndex =getIndexOfV(vSrc);intn =arrayV.length;for(inti =0;i <n;i++){//i下标正好是起点  则不进行路径的打印if(i !=srcIndex){ArrayList<Integer>path =newArrayList<>();intpathI =i;while(pathI !=srcIndex){path.add(pathI);pathI =pPath[pathI];}path.add(srcIndex);Collections.reverse(path);for(intpos :path){System.out.print(arrayV[pos]+" -> ");}System.out.println(dist[i]);}}}publicstaticvoidtestGraphDijkstra(){Stringstr ="syztx";char[]array =str.toCharArray();GraphByMatrixg =newGraphByMatrix(str.length(),true);g.initArrayV(array);g.addEdge('s','t',10);g.addEdge('s','y',5);g.addEdge('y','t',3);g.addEdge('y','x',9);g.addEdge('y','z',2);g.addEdge('z','s',7);g.addEdge('z','x',6);g.addEdge('t','y',2);g.addEdge('t','x',1);g.addEdge('x','z',4);int[]dist =newint[array.length];int[]parentPath =newint[array.length];g.dijkstra('s',dist,parentPath);g.printShortPath('s',dist,parentPath);}
运行结果为：
构建的图为过程演示时的图。

显然正确🎉🎉🎉
二、Dijkstra 算法
二、for(inti =0;i <g.size;i++){Arrays.fill(g.matrix[i],Integer.MAX_VALUE);}g.addEdge('1','2',3);g.addEdge('1','3',8);g.addEdge('1','5',-4);g.addEdge('2','4',1);g.addEdge('2','5',7);g.addEdge('3','2',4);g.addEdge('4','1',2);g.addEdge('4','3',-5);g.addEdge('5','4',6);int[][]dist =newint[array.length][array.length];int[][]parentPath =newint[array.length][array.length];g.floyWarShall(dist,parentPath);for(inti =0;i <array.length;i++){g.printShortPath(array[i],dist[i],parentPath[i]);}}

运行结果如下：

下图为测试图例的过程图。

• 算法流程：

Floyd-Warshall 算法的原理是动态规划。时间复杂度为 O（n ^ 3）。涉及到三个算法：

1. 单源最短路径：Dijkstra 算法（迪杰斯特拉算法）（不能解决负权图）
2. 单源最短路径：Bellman-Ford 算法（贝尔曼-福特算法）（可以解决负权图）
3. 多源最短路径：Floyd-Warshall 算法（弗洛伊德算法）（可以解决负权图）

注意：本文采用的图是邻接矩阵实现的。

设 D(i,j,k) 为从 i 到 j 的只以(1…k)集合中的节点为中间节点的最短路径的长度。

过程演示如下图：

• 代码如下：

/**     * @param vSrc  起点     * @param dist  存储从起点到各个顶点的最小权值     * @param pPath 存储各个顶点到起点的最短权值路径     */publicvoiddijkstra(charvSrc,int[]dist,int[]pPath){//用来标记已经确定的点boolean[]vis =newboolean[size];//获取起点对应下标intsrcIndex =getVIndex(vSrc);//初始化 dist 和 pPathArrays.fill(dist,Integer.MAX_VALUE);Arrays.fill(pPath,-1);//最终结果为 -1 说明起点到达不了//起点到起点为 0dist[srcIndex]=0;pPath[srcIndex]=srcIndex;//填写 distfor(inti =0;i <size;i++){//一共要填写 size 次//确定一条最短的路径intmin =Integer.MAX_VALUE;intu =srcIndex;for(intv =0;v <size;v++){if(vis[v]==false&&min >dist[v]){min =dist[v];u =v;}}vis[u]=true;//进行松弛操作 + 填写 pPath//一个顶点出度最大为 size，把不存在的排除即可for(intv =0;v <size;v++){if(vis[v]==false&&matrix[u][v]!=Integer.MAX_VALUE&&dist[u]+matrix[u][v]<dist[v]){dist[v]=dist[u]+matrix[u][v];pPath[v]=u;}}}}

• 测试 Dijkstra 算法：

通过打印最短路的顶点组成和最短路的长度，即可验证正确性。