最短路算法详解(Dijkstra 算法,Bellman-Ford 算法,Floyd-Warshall 算法)

2024-08-31 14:36

本文主要是介绍最短路算法详解(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

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int