当前位置: 首页 > news >正文

数据结构-图-最短路径问题

最短路径问题

  • 单源最短路径
    • Dijkstra
      • 算法原理
      • 代码实现
    • Bellman-Ford
      • 算法原理
      • 代码实现
      • SPFA优化
      • SPFA代码实现
  • 多元最短路径
    • Floyd-Warshall
      • 算法原理
      • 代码实现

单源最短路径

🚀最短路径:从图G的某个顶点出发到达另一个顶点的最短路径,其中最短是指路径上边的权值和最小。
🚀单源最短路径:从图G中的某一顶点出发到达其余顶点的最短路径。

Dijkstra

算法原理

🚀针对一个带权有向图,将所有的顶点划分为两个集合S和Q,S是已经确定最短路径的顶点结合,Q是还未确定最短路径的顶点集合。每次从Q中找出一个从起点s到达该结点代价最小(权值和最小)的结点u(可见迪杰斯特拉算法同样采取的是贪心策略),将u从集合Q中移除,并放入S中,对u所邻接的顶点做一次松弛操作。松弛操作即对结点u的邻接点v,判断从起点s到u的代价+u到v的代价是否小于s到v的代价,若小于那么对s到v的代价替换为s到u的代价+u到v的代价。这样依次从Q中选出结点u,直到Q为空为止。

算法特点:比较与其他最短路径的算法,迪杰斯特拉算法的效率较优。但是,此算法只能用于没有负权值的图。

在这里插入图片描述

源点为s,即求s到达其他顶点的最短路径。在初始时,s到达其他边的路径长度均为无穷大 ,到达自身的距离为0。

算法执行过程

在这里插入图片描述

代码实现

void Dijkstra(const V& src, std::vector<W>& dist, std::vector<int>& parent_path) {//初始化工作size_t n = _vertex.size();size_t srci = this->GetVertexIndex(src);dist.resize(n, W_MAX);dist[srci] = 0;parent_path.resize(n, -1);std::vector<bool> S(n, false); //已选出的顶点集合Sfor (size_t i = 0; i < n; i++) {//从dist中选出最短的一条边,S->usize_t u = -1;W min_eg = W_MAX;for (size_t j = 0; j < n; j++) {if (dist[j] < min_eg && false == S[j]) {u = j;min_eg = dist[j];}}//将这个顶点添加到S集合中S[u] = true;//更新从起始点srci能够到达的其他点的最短路径dist数组for (size_t i = 0; i < n; i++) {if (_matrix[u][i] != W_MAX && false == S[i] && dist[u] + _matrix[u][i] < dist[i]) {dist[i] = dist[u] + _matrix[u][i];parent_path[i] = u;}}}
}

dist数组和parent_path数组解释:将源点s到达其他顶点的最短路径数值存储在dist数组中,dist[i]即为源点s到达i号顶点的最短距离。parent_path数组用来记录源点s到达其他顶点的最短路径,采用的是双亲表示法,即该结点存储的内容为源点s到达这个结点路径上的上一个结点的下标。

🚀上面例子中最终两个数值的内容如下:

在这里插入图片描述

Bellman-Ford

算法原理

🚀迪杰斯特拉算法不能解决带负权值路径的情况,贝尔曼算法可以解决这一问题。相比于迪杰斯特拉的贪心策略,贝尔曼算法是一种较为暴力的解法,即对每一个结点都做一次松弛操作,但是一轮松弛操作往往不能得到最终结果,存在最短路径于最短路径权值和对应不上的情况,所以要经过多轮更新才能得到最终结果。最多轮次为n-1轮(n:顶点个数),如果说第n轮更新还能有顶点松弛成功说明存在权值和为负数的环路情况,这种情况贝尔曼算法也是解决不了的(权值和为负数的环路意味着每轮更新都能得到一个更小的结果,是无休止的)。

只经过一轮更新不能的到最终结果的例子

在这里插入图片描述

产生上图中这样结果的原因在于更新源点s到达z顶点的最短路径是由对t顶点的邻接顶点做松弛操作得到的,但是在更新源点s到达z的最短路径之后,在对x的邻接顶点做松弛操作的时候,又重新修改了源点s到达t顶点的最短路径,此时在parent_path数组中t位置的数据修改成了x的下标,同样也因此导致了s到达z顶点的路径于路径上的权值和不一致的情况。所以要对t的邻接顶点重新做一次松弛操作,上面这种情况再对t的邻接顶点做一次松弛操作就可以解决问题,但是对于其他更为复杂的问题可能仍旧需要新一轮的松弛操作。那么,松弛操作轮数的上限是多少次呢?n - 1次因为源点出发到达另一个顶点的最短路径至多经过n - 1条边,所以至多经过n - 1轮的更新就能得到最终结果,但是如果第n轮时仍旧存在到达某个点的最短路径发生了更新,那么就说明存在权值和为负数的环路问题。

代码实现

bool Bellman(const V& src, std::vector<W>& dist, std::vector<int>& parent_path) {//初始化结构size_t n = _vertex.size();size_t srci = this->GetVertexIndex(src);dist.resize(n, W_MAX);dist[srci] = 0;parent_path.resize(n, -1);//寻找最短路径for (size_t k = 0; k < n - 1; ++k) {bool update = false;//update小的优化--如果此轮更新中没有任何一条边松弛成功,此时就可以break退出std::cout << "第" << k + 1 << "轮更新: \n";for (size_t i = 0; i < n; i++) {for (size_t j = 0; j < n; j++) {if (_matrix[i][j] != W_MAX && dist[i] + _matrix[i][j] < dist[j]) {update = true;dist[j] = dist[i] + _matrix[i][j];std::cout << i << "->" << j << ":" << dist[j] << std::endl;parent_path[j] = i;}}}if (false == update) {break;}}//如果经过n-1轮还能进行更新说明出现了负权值环路问题for (size_t i = 0; i < n; i++) {for (size_t j = 0; j < n; j++) {if (_matrix[i][j] != W_MAX && dist[i] + _matrix[i][j] < dist[j]) {return false;}}}return true;
}

SPFA优化

🚀在上面分析一轮的松弛操作可能不能得到最终结果的问题时,解决方案就是再对t顶点的邻接顶点做一次松弛操作即可,并不用再对其他顶点做一次松弛操作,也就是说如果要在下一轮中再次对某个顶点的邻接顶点做松弛操作,那么这个顶点一定在本轮中得到了最短路径的更新,否则其不会对其他顶点产生影响。

🚀SPFA算法就是对上面代码中写的贝尔曼算法的一个优化,就是说如果要在下一轮中再次对某个顶点的邻接顶点做松弛操作,那么这个顶点一定在本轮中得到了最短路径的更新,所以在第一轮更新中所有顶点都需要更新,把所有的顶点都入队列,在后续的更新中,如果某个顶点在本轮没有被更新那么其也不会对其他顶点产生影响,就不用再次入队列,相反需要再次入队列, 这样循环置队列为空即可。

SPFA代码实现

void BellmanSPFA(const V& src, std::vector<W>& dist, std::vector<int>& parent_path) {//初始化结构size_t n = _vertex.size();size_t srci = this->GetVertexIndex(src);dist.resize(n, W_MAX);dist[srci] = 0;parent_path.resize(n, -1);std::queue<size_t> q;std::vector<bool> flag(n, false);q.push(srci);flag[srci] = true;while (!q.empty()) {size_t top = q.front();q.pop();flag[top] = false;for (size_t i = 0; i < n; i++) {if (_matrix[top][i] != W_MAX && dist[top] + _matrix[top][i] < dist[i]) {dist[i] = dist[top] + _matrix[top][i];parent_path[i] = top;if (flag[i] == false) {q.push(i);flag[i] = true;}}}}
}

多元最短路径

Floyd-Warshall

算法原理

🚀佛洛依德算法是一个解决多源的最短路径问题的经典算法,它能够计算出每个顶点到达其余顶点的最短路径,对应用场景通常是带负权值的多源最短路径问题。

🚀佛洛依德算法采用的是动态规划的思想,顶点i到达顶点j的最短路径上至少经过了0个其他顶点,至多经过了n - 2个其他顶点,其状态标识可以定义为dp[i][j][m],标识顶点i到达顶点j的最短路径上经过了k个其余顶点,其余顶点就是除了起始顶点和终止顶点的其他顶点记作k(k有n-2种取值可能),所以如果i到j的最短路径经过k,那么dp[i][j][m] = dp[i][k][m-1] + dp[k][j][m-1],如果i到j的最短路径不经过k,dp[i][j][m] = dp[i][j][m-1],所以最终dp[i][j][m] = min(dp[i][j][m-1],dp[i][k][m-1]+dp[k][j][m-1])。在正常写代码时通常将其优化为二维的动态规划,因为第三维的m总是依赖于m-1的。

代码实现

void Floyd(std::vector<std::vector<W>>& dist, std::vector<std::vector<int>>& parent_path) {//初始化结构size_t n = _vertex.size();dist.resize(n);parent_path.resize(n);for (size_t i = 0; i < n; ++i) {dist[i].resize(n, W_MAX);parent_path[i].resize(n, -1);}//初始化直接相连的边for (size_t i = 0; i < n; i++) {for (size_t j = 0; j < n; j++) {if (_matrix[i][j] != W_MAX) {dist[i][j] = _matrix[i][j];parent_path[i][j] = i;}if (i == j) {dist[i][j] = 0;}}}//动态规划for (size_t k = 0; k < n; ++k) {for (size_t i = 0; i < n; ++i) {for (size_t j = 0; j < n; ++j) {if (dist[i][k] != W_MAX && dist[k][j] != W_MAX &&dist[i][k] + dist[k][j] < dist[i][j]) {//更新dist[i][j] = dist[i][k] + dist[k][j];parent_path[i][j] = parent_path[k][j];}}}}
}

相关文章:

数据结构-图-最短路径问题

最短路径问题 单源最短路径Dijkstra算法原理代码实现 Bellman-Ford算法原理代码实现SPFA优化SPFA代码实现 多元最短路径Floyd-Warshall算法原理代码实现 单源最短路径 &#x1f680;最短路径&#xff1a;从图G的某个顶点出发到达另一个顶点的最短路径&#xff0c;其中最短是指…...

弹性资源组件elastic-resource设计(二)-集群

简介 弹性资源组件提供动态资源能力,是分布式系统关键基础设施,分布式datax,分布式索引,事件引擎都需要集群和资源的弹性资源能力,提高伸缩性和作业处理能力。 本文介绍弹性资源组件的设计,包括架构设计和详细设计,指导开发人员代码开发,设计基于《flink原理源码分析(一…...

Flink学习笔记(一):Flink重要概念和原理

文章目录 1、Flink 介绍2、Flink 概述3、Flink 组件介绍3.1、Deploy 物理部署层3.2、Runtime 核心层3.3、API&Libraries 层3.4、扩展库 4、Flink 四大基石4.1、Checkpoint4.2、State4.3、Time4.4、Window 5、Flink 的应用场景5.1、Event-driven Applications【事件驱动】5.…...

网络中的一些基本概念

数据共享本质是网络数据传输 &#xff0c;即计算机之间通过网络来传输数据&#xff0c;也称为 网络通信 。 根据网络互连的规模不同&#xff0c;可以划分为局域网和广域网。 局域网 LAN 局域网&#xff0c;即 Local Area Network &#xff0c;简称 LAN 。 Local 即标识了局…...

mysql中varchar长度为多少

一. varchar存储规则&#xff1a; 4.0版本以下&#xff0c;varchar(20)&#xff0c;指的是20字节&#xff0c;如果存放UTF8汉字时&#xff0c;只能存6个&#xff08;每个汉字3字节&#xff09; 5.0版本以上&#xff0c;varchar(20)&#xff0c;指的是20字符&#xff0c;无论存…...

python+selenium实现UI自动化(入门篇)

一、基础准备。 python环境安装&#xff0c;参考&#xff1a;CSDN pycharm安装&#xff0c;参考&#xff1a;CSDN 谷歌浏览器驱动配置&#xff0c;参考&#xff1a;CSDN二、新建pycharm项目 截图中&#xff0c;上面是项目地址&#xff08;可以提前在指定位置创建文件夹&#xf…...

深度学习基础知识 nn.Sequential | nn.ModuleList | nn.ModuleDict

深度学习基础知识 nn.Sequential &#xff5c; nn.ModuleList &#xff5c; nn.ModuleDict 1、nn.Sequential 、 nn.ModuleList 、 nn.ModuleDict 类都继承自 Module 类。2、nn.Sequential、nn.ModuleList 和 nn.ModuleDict语法3、Sequential 、ModuleDict、 ModuleList 的区别…...

【DevOps】搭建你的第一个 Docker 应用栈

搭建你的第一个 Docker 应用栈 1.Docker 集群部署2.第一个 Hello World2.1 获取应用栈各节点所需镜像2.2 应用栈容器节点互联2.3 应用栈容器节点启动2.4 应用栈容器节点的配置2.4.1 Redis Master 主数据库容器节点的配置2.4.2 Redis Slave 从数据库容器节点的配置2.4.3 Redis 数…...

软件测试职业生涯需要编写的全套文档模板,收藏这一篇就够了 ~

作为一名测试工程师&#xff0c;在整个的职业生涯中&#xff0c;会涉及到各种不同类型的文档编写&#xff0c;大体包括如下&#xff1a; 对应文档模板及文档编写视频如下&#xff1a; 一、测试岗位必备的文档 在一个常规的软件测试流程中&#xff0c;会涉及到测试计划、测试方…...

【Kubernetes】Pod——k8s中最重要的对象之一

Pod是什么&#xff1f;如何使用Pod&#xff1f;资源共享和通信Pod 中的存储Pod 联网&#xff1a;跨 Pod 通信 静态 Pod感谢 &#x1f496; Pod是什么&#xff1f; Pod是k8s中创建和管理的、最小的可部署的计算单元。它包含一个或多个容器。就像豌豆荚里面包含了多个豌豆一样。…...

vue-cli-service: command not found问题解决

解决方案&#xff1a;重新安装一下&#xff1a; npm install -g vue/cli...

每日一练 | 华为认证真题练习Day117

1、缺省情况下&#xff0c;广播网络上OSPF协议Deadtime是&#xff1f; A. 20s B. 40s C. 10s D. 30s 2、当两台OSPF路由器形成TWO-WAY邻居关系时&#xff0c;LSDB已完成同步&#xff0c;但是SPF算法尚未运行。 A. 对 B. 错 3、以下哪种协议不属于文件传输协&#xff1f; …...

【JVM】垃圾回收(GC)详解

垃圾回收&#xff08;GC&#xff09;详解 一. 死亡对象的判断算法1. 引用计数算法2. 可达性分析算法 二. 垃圾回收算法1. 标记-清除算法2. 复制算法3. 标记-整理算法4. 分代算法 三. STW1. 为什么要 STW2. 什么情况下 STW 四. 垃圾收集器1. CMS收集器&#xff08;老年代收集器&…...

阿里云服务器公网带宽多少钱1M?

阿里云服务器公网带宽计费模式按固定带宽”计费多少钱1M&#xff1f;地域不同带宽价格不同&#xff0c;北京、杭州、深圳等大陆地域价格是23元/Mbps每月&#xff0c;中国香港1M带宽价格是30元一个月&#xff0c;美国硅谷是30元一个月&#xff0c;日本东京1M带宽是25元一个月&am…...

应用DeepSORT实现目标跟踪

在ByteTrack被提出之前&#xff0c;可以说DeepSORT是最好的目标跟踪算法之一。本文&#xff0c;我们就来应用这个算法实现目标跟踪。 DeepSORT的官方网址是https://github.com/nwojke/deep_sort。但在这里&#xff0c;我们不使用官方的代码&#xff0c;而使用第三方代码&#…...

Beyond Compare 4 30天评估到期 解决方法

Beyond Compare 4 用习惯了&#xff0c;突然提示评估到期了&#xff0c;糟心&#x1f604; 该方法将通过修改注册表&#xff0c;使BeyondCompare 版本4可以恢复到未评估状态&#xff0c;使其可以持续使用30天评估&#x1f604;。 修改注册表 第一步&#xff1a;打开注册表。 在…...

化妆品用乙基己基甘油全球市场总体规模2023-2029

乙基己基甘油又名辛氧基甘油&#xff0c;分子式 C11H24O3&#xff0c;分子量 204.306&#xff0c;沸点 325℃&#xff0c;密度 0.962&#xff0c;无色液体&#xff0c;涂抹性能适中的润肤剂、保湿剂及润湿剂。它能够在提高配方滋润效果的同时又具有柔滑的肤感。加入在某些膏霜体…...

springboot家政服务管理平台springboot29

大家好✌&#xff01;我是CZ淡陌。一名专注以理论为基础实战为主的技术博主&#xff0c;将再这里为大家分享优质的实战项目&#xff0c;本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路…...

【网络安全】如何保护IP地址?

使用防火墙是保护IP地址的一个重要手段。防火墙可以监控和过滤网络流量&#xff0c;并阻止未经授权的访问。一家网络安全公司的研究显示&#xff0c;超过80%的企业已经部署了防火墙来保护他们的网络和IP地址。 除了防火墙&#xff0c;定期更新操作系统和应用程序也是保护IP地址…...

2023年失业了,想学一门技术可以学什么?

有一个朋友&#xff0c;大厂毕业了&#xff0c;原本月薪估计有5w吧&#xff0c;年终奖也不错&#xff0c;所以早早的就买了房生了娃&#xff0c;一直是人生赢家的姿态。 但是今年突然就被毕业了&#xff0c;比起房货还有个几百万没还来说&#xff0c;他最想不通的是自己的价值…...

MySQL-MVCC(Multi-Version Concurrency Control)

MySQL-MVCC&#xff08;Multi-Version Concurrency Control&#xff09; MVCC&#xff08;多版本并发控制&#xff09;&#xff1a;为了解决数据库并发读写和数据一致性的问题&#xff0c;是一种思想&#xff0c;可以有多种实现方式。 核心思想&#xff1a;写入时创建行的新版…...

ArcGIS中的镶嵌数据集与接缝线

此处介绍一种简单方法&#xff0c;根据生成的轮廓线来做镶嵌数据集的拼接。 一、注意修改相邻影像的上下重叠。注意修改ZOrder和每幅影像的范围。 二、修改新的镶嵌线并且导出影像文件。 三、还有其他方法和注意事项。...

网络安全工程师自主学习计划表(具体到阶段目标,保姆级安排,就怕你学不会!)

前言 接下来我将给大家分享一份网络安全工程师自学计划指南&#xff0c;全文将从学习路线、学习规划、学习方法三个方向来讲述零基础小白如何通过自学进阶网络安全工程师&#xff0c;全文篇幅有点长&#xff0c;同学们可以先点个收藏&#xff0c;以免日后错过了。 目录 前言…...

Linux 根据 PID 查看进程名称

ps aux | grep PID...

Python二级 每周练习题21

练习一: 提示用户输入两个正整数&#xff0c;编程求出介于这两个数之间的所有质数并打印输出。 显示格式为“*数是质数。” 答案: x(int(input(请输入第一个正整数:)),int(input(请输入第二个正整数:))) #变量x存放input输入的两个整数的元组 Num1min(x) #判断输入数字…...

【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是螺旋矩阵&#xff0c;使用【二维数组】这个基本的数据结构来实现 螺旋矩阵【EASY】 二维数组的结构特性入手 题干 解题思路 根据题目示例 mat…...

LED灯实验--汇编

asm-led.S .text .global _start _start: /* 1. led灯的初始化 *//* 1.1 使能GPIOE、DPIOF外设控制器的时钟 */ldr r0, 0x50000A28ldr r1, [r0]orr r1, r1, #(0x3 << 4)str r1, [r0]/* 1.2 设置PE10、PE8、PF10引脚为输出模式 */ldr r0, 0x50006000ldr r1, [r0]bic r1,…...

Android多线程学习:线程池(一)

一、概念 线程池&#xff1a;创建并维护一定数量的空闲线程&#xff0c;当有需要执行的任务&#xff0c;就交付给线程池中的一个线程&#xff0c;任务执行结束后&#xff0c;该线程也不会死亡&#xff0c;而是回到线程池中重新变为空闲状态。 线程池优点&#xff1a; 1、重用…...

网络安全(黑客技术)—小白自学笔记

1.网络安全是什么 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 2.网络安全市场 一、是市场需求量高&#xff1b; 二、则是发展相对成熟入…...

掌握核心技巧就能创建完美的目录!如何在Word中自动创建目录

目录是Word布局的一个重要因素&#xff0c;尤其是在编写较长的文档时。那么&#xff0c;你如何在你的作品中添加目录呢&#xff1f;在这篇文章中&#xff0c;我将分享一些基于Word2016自动创建目录的经验。希望它能或多或少地帮到你。 自动创建目录 1、输入目录文本的名称&am…...