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

2024-08-31 14:36
文章标签 算法 详解 短路 dijkstra floyd bellman ford warshall

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

文章目录

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

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

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

  1. 单源最短路径：Dijkstra 算法（迪杰斯特拉算法）（不能解决负权图）
  2. 单源最短路径：Bellman-Ford 算法（贝尔曼-福特算法）（可以解决负权图）
  3. 多源最短路径：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)集合中的节点为中间节点的最短路径的长度。

  1. 若最短路径不经过 k，则 D(i,j,k) = D(i,j,k - 1)。
  2. 若最短路径经过 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]);}}

运行结果如下：
在这里插入图片描述

下图为测试图例的过程图。
在这里插入图片描述
通过对比可以发现，我们的运行结果是正确的（路径会差 1，因为下标是从 0 开始的）。

参考资料：OI-wiki。

结语：
其实写博客不仅仅是为了教大家，同时这也有利于我巩固知识点，和做一个学习的总结，由于作者水平有限，对文章有任何问题还请指出，非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。
在这里插入图片描述

这篇关于最短路算法详解（Dijkstra 算法，Bellman-Ford 算法，Floyd-Warshall 算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1124175。

相关文章

MySQL数据库双机热备的配置方法详解

MySQL数据库双机热备的配置方法详解

《MySQL数据库双机热备的配置方法详解》在企业级应用中,数据库的高可用性和数据的安全性是至关重要的,MySQL作为最流行的开源关系型数据库管理系统之一,提供了多种方式来实现高可用性,其中双机热备（M... 目录1. 环境准备1.1 安装mysql1.2 配置MySQL1.2.1 主服务器配置1.2.2 从
阅读更多...
Linux kill正在执行的后台任务 kill进程组使用详解

Linux kill正在执行的后台任务 kill进程组使用详解

《Linuxkill正在执行的后台任务kill进程组使用详解》文章介绍了两个脚本的功能和区别,以及执行这些脚本时遇到的进程管理问题,通过查看进程树、使用`kill`命令和`lsof`命令,分析了子... 目录零. 用到的命令一. 待执行的脚本二. 执行含子进程的脚本，并kill2.1 进程查看2.2 遇到的
阅读更多...
MyBatis常用XML语法详解

MyBatis常用XML语法详解

《MyBatis常用XML语法详解》文章介绍了MyBatis常用XML语法,包括结果映射、查询语句、插入语句、更新语句、删除语句、动态SQL标签以及ehcache.xml文件的使用,感兴趣的朋友跟随小... 目录1、定义结果映射2、查询语句3、插入语句4、更新语句5、删除语句6、动态 SQL 标签7、ehc
阅读更多...
详解SpringBoot+Ehcache使用示例

详解SpringBoot+Ehcache使用示例

《详解SpringBoot+Ehcache使用示例》本文介绍了SpringBoot中配置Ehcache、自定义get/set方式,并实际使用缓存的过程,文中通过示例代码介绍的非常详细,对大家的学习或者... 目录摘要概念内存与磁盘持久化存储：配置灵活性：编码示例引入依赖：配置ehcache.XML文件：配置
阅读更多...
从基础到高级详解Go语言中错误处理的实践指南

从基础到高级详解Go语言中错误处理的实践指南

《从基础到高级详解Go语言中错误处理的实践指南》Go语言采用了一种独特而明确的错误处理哲学,与其他主流编程语言形成鲜明对比,本文将为大家详细介绍Go语言中错误处理详细方法,希望对大家有所帮助... 目录1 Go 错误处理哲学与核心机制1.1 错误接口设计1.2 错误与异常的区别2 错误创建与检查2.1 基础
阅读更多...
k8s按需创建PV和使用PVC详解

k8s按需创建PV和使用PVC详解

《k8s按需创建PV和使用PVC详解》Kubernetes中,PV和PVC用于管理持久存储,StorageClass实现动态PV分配,PVC声明存储需求并绑定PV,通过kubectl验证状态,注意回收... 目录1.按需创建 PV（使用 StorageClass）创建 StorageClass2.创建 PV
阅读更多...
Python版本信息获取方法详解与实战

Python版本信息获取方法详解与实战

《Python版本信息获取方法详解与实战》在Python开发中,获取Python版本号是调试、兼容性检查和版本控制的重要基础操作,本文详细介绍了如何使用sys和platform模块获取Python的主... 目录1. python版本号获取基础2. 使用sys模块获取版本信息2.1 sys模块概述2.1.1
阅读更多...
一文详解Python如何开发游戏

一文详解Python如何开发游戏

《一文详解Python如何开发游戏》Python是一种非常流行的编程语言,也可以用来开发游戏模组,：本文主要介绍Python如何开发游戏的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录一、python简介二、Python 开发 2D 游戏的优劣势优势缺点三、Python 开发 3D
阅读更多...
Redis 基本数据类型和使用详解

Redis 基本数据类型和使用详解

《Redis基本数据类型和使用详解》String是Redis最基本的数据类型,一个键对应一个值,它的功能十分强大,可以存储字符串、整数、浮点数等多种数据格式,本文给大家介绍Redis基本数据类型和... 目录一、Redis 入门介绍二、Redis 的五大基本数据类型2.1 String 类型2.2 Hash
阅读更多...
Java中的.close()举例详解

Java中的.close()举例详解

《Java中的.close()举例详解》.close()方法只适用于通过window.open()打开的弹出窗口,对于浏览器的主窗口,如果没有得到用户允许是不能关闭的,：本文主要介绍Java中的.... 目录当你遇到以下三种情况时，一定要记得使用 .close()：用法作用举例如何判断代码中的 input
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2