最短路算法详解（Dijkstra 算法，Bellman-Ford 算法，Floyd-Warshall 算法）

本文主要是介绍最短路算法详解（Dijkstra 算法，Bellman-Ford 算法，Floyd-Warshall 算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

一、Dijkstra 算法
二、Bellman-Ford 算法
三、Floyd-Warshall 算法

由于文章篇幅有限，下面都只给出算法对应的部分代码，需要全部代码调试参考的请点击：图的源码

最短路径问题：从在带权图的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。涉及到三个算法：

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

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

一、Dijkstra 算法

算法概括：

Dijkstra 是一种求解非负权图上单源最短路径的算法。

算法流程：

其过程为：将结点分成两个集合，已确定最短路长度的点集（记为 S 集合）和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。

需要对 dist 数组（存储最短路的长度）进行初始化，除了起点设置为 0 外，其它的都设置为无穷大。

接着重复如下操作：

从 T 集合中，选取一个最短路长度最小的节点，移动到 S 集合中。
对那些刚刚加入 S 集合的结点的所有出边执行松弛操作。

直到 T 集合为空，算法结束。

时间复杂度：

每次确定一个顶点 O（n），并松弛其连接出去的所有边（最多有 n - 1条），其时间复杂度为 O（n ^ 2）。

松弛操作：
对于起点 B 到达点 A，松弛操作对应如下的式子：dis(A) = min(dis(A) , dis(C ) + 边 CA），当确定一个顶点的最短路径后，对其连出去的所有边进行松弛操作。

过程演示如下图：

代码如下：

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

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

public void printShortPath(char vSrc,int[] dist,int[] pPath) {int srcIndex = getIndexOfV(vSrc);int n = arrayV.length;for (int i = 0; i < n; i++) {//i下标正好是起点  则不进行路径的打印if(i != srcIndex) {ArrayList<Integer> path = new ArrayList<>();int pathI = i;while (pathI != srcIndex) {path.add(pathI);pathI = pPath[pathI];}path.add(srcIndex);Collections.reverse(path);for (int pos : path) {System.out.print(arrayV[pos]+" -> ");}System.out.println(dist[i]);}}}public static void testGraphDijkstra() {String str = "syztx";char[] array = str.toCharArray();GraphByMatrix g = new GraphByMatrix(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 = new int[array.length];int[] parentPath = new int[array.length];g.dijkstra('s', dist, parentPath);g.printShortPath('s', dist, parentPath);}

运行结果为：

构建的图为过程演示时的图。

显然正确🎉🎉🎉

二、Bellman-Ford 算法

算法概括：

Bellman–Ford 算法是一种基于松弛操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

算法流程：

Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

时间复杂度：

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 + 1，而最短路的边数最多为 n - 1，因此整个算法最多执行 n - 1 轮松弛操作。故总时间复杂度为 O（n * m）。其中 n 为顶点个数，m 为边的个数。

代码如下：

/**** @param vSrc 起点* @param dist 存储从起点到各个顶点的最小权值* @param pPath 存储各个顶点到起点的最短权值路径* @return 返回 true 表示该图不存在负权回路，返回 false 表示该图存在负权回路*/public boolean bellmanFord(char vSrc, int[] dist, int[] pPath) {//获取顶点下标int srcIndex = getVIndex(vSrc);//初始化数据Arrays.fill(dist, Integer.MAX_VALUE);Arrays.fill(pPath, -1);dist[srcIndex] = 0;pPath[srcIndex] = srcIndex;//松弛操作//进行 size 次for (int k = 0; k < size; k++) {//遍历每条边for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {if (matrix[i][j] != Integer.MAX_VALUE && dist[i] + matrix[i][j] < dist[j]) {dist[j] = dist[i] + matrix[i][j];pPath[j] = i;}}}}//判断是否存在负回路for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {if (matrix[i][j] != Integer.MAX_VALUE && dist[i] + matrix[i][j] < dist[j]) {return false;//存在负回路}}}return true;//不存在负回路}

测试 Bellman-Ford 算法：

下面的测试案例就是根据这张图进行设计的。

public static void testGraphBellmanFord() {String str = "syztx";char[] array = str.toCharArray();GraphByMatrix g = new GraphByMatrix(str.length(), true);g.initArrayV(array);for (int i = 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 = new int[array.length];int[] parentPath = new int[array.length];boolean fig = g.bellmanFord('s', dist, parentPath);if (fig) {g.printShortPath('s', dist, parentPath);} else {System.out.println("存在负权回路");}}

运行结果如下：

三、Floyd-Warshall 算法

算法概括：

Floyd-Warshall 算法是用来求任意两个结点之间的最短路的。适用于任何图，不管有向无向，边权正负，但是最短路必须存在（不能有个负环），复杂度比较高。

算法流程：

Floyd-Warshall 算法的原理是动态规划。

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

若最短路径不经过 k，则 D(i,j,k) = D(i,j,k - 1)。
若最短路径经过 k，则 D(i,j,k) = D(i,k,k - 1) + D(k,j,k - 1)。（k - 1 不影响起点和终点取 k）

因此，D(i,j,k) = min(D(i,j,k - 1)，D(i,k,k - 1) + D(k,j,k - 1))。

在实际算法中，为了节省空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

时间复杂度：

k 的取值从 1 到 n，每次 k 都要进行一次完整的动态规划。时间复杂度为 O（n ^ 3）。

代码如下：

/**** @param dist 存储各个顶点之间的最小权值* @param pPath 存储各个顶点之间的最短权值路径*/public void floyWarShall(int[][] dist, int[][] pPath) {//初始化for (int i = 0; i < size; i++) {Arrays.fill(dist[i], Integer.MAX_VALUE);Arrays.fill(pPath[i], -1);}//将边填入到 dist 数据，给后续动态规划初始化for (int i = 0; i < size; i++) {for (int j = 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 (int k = 0; k < size; k++) {for (int i = 0; i < size; i++) {for (int j = 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 (int i = 0; i < size; i++) {for (int j = 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 (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {System.out.print(pPath[i][j] + " ");}System.out.println();}System.out.println("=================");}

测试 Floyd-Warshall 算法：

测试图例如下：

public static void testGraphFloydWarShall() {String str = "12345";char[] array = str.toCharArray();GraphByMatrix g = new GraphByMatrix(str.length(), true);g.initArrayV(array);//没有边，设置为 最大值。for (int i = 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 = new int[array.length][array.length];int[][] parentPath = new int[array.length][array.length];g.floyWarShall(dist, parentPath);for (int i = 0; i < array.length; i++) {g.printShortPath(array[i],dist[i],parentPath[i]);}}