【图论】迪杰特斯拉算法
文章目录
- 迪杰特斯拉算法
- 主要特点
- 基本思想
- 算法步骤
- 示例
- 实现迪杰斯特拉算法
- 基本步骤
- 算法思路
- 总结

迪杰特斯拉算法
迪杰特斯拉算法是由荷兰计算机科学家艾兹赫尔·迪杰特斯拉(Edsger W. Dijkstra)在1956年提出的,用于解决单源最短路径问题的经典算法。该算法的目标是从一个起始顶点找到到图中其他顶点的最短路径。
主要特点
- 适用于带权图,其中权重为非负数。(为什么只适用于非负数,因为迪杰斯特拉的思想是贪心测量,当有负权引入的时候,贪心策略将不再适用)
- 解决从单个源点到其他所有顶点的最短路径问题。
- 时间复杂度:当使用优先队列(例如堆)时,复杂度为 O ( E log V ) O(E \log V) O(ElogV),其中 V V V 为顶点数量, E E E 为边的数量。
基本思想
Dijkstra算法通过不断探索距离最近的顶点,逐步扩展其最短路径的已知范围,直到找到从源点到所有其他顶点的最短路径。该算法基于贪心策略:每一步选择尚未处理的、距离源点最近的顶点进行扩展。
算法步骤
-
初始化:
- 将起始顶点的距离设为0,其余所有顶点的距离设为∞(表示不可达)。
- 使用一个优先队列(或最小堆)来存储顶点及其当前的最短距离。
-
取距离源点最近的顶点,并标记为已处理。
-
对于该顶点的每个邻接顶点,更新其最短距离(如果通过当前顶点可以获得更短的路径,则更新距离)。
-
重复步骤2和3,直到所有顶点都被处理过,或优先队列为空。
示例

实现迪杰斯特拉算法
基本步骤
首先假设我们有如下的一个图:

灰色的点代表起点,我们需要从起点开始算每个点到起点的最短路径。
第一步按照迪杰斯特拉的表述应该将起点到起点的最短路径初始化为0,起点到另外其他点的距离初始化为正无穷。

这里我们更新完s点之后,应该更新和s点相连的点的最短路径了,由于之前s到t点和到y点的最短路径是正无穷,由于st和sy都小于两个最短路径,所以更新两个最短路径。

根据贪心策略,更新出来的两个最短路径,sy更小,所以我们应该更新y相连的路径。

所以接下来我们应该更新y连接的点的最短路径。

由于原本s到t的最短路径是10,但是现在的最短路径更新了之后是8,所以更新结果,由于之前s到x的最短路径是正无穷,所以现在将最短路径更新为14,s到z 也是相同的,因为之前的最短路径是正无穷,所以现在将最短路径更新为7.
在这三条最短路径中选择最短的那条:

这里就应该以z为新的起点

更新z连接的顶点,z一共有两条边,一条是zs,一条是zx,由于s到s是最近的0,所以这里不需要更新,由于之前s到x的距离是14,所以这里更新s到x的距离。
接下来再从剩下的边中,选择最小的路径。

从t点开始只有一条路径,所以这里t到x,tx是1,由于之前的st的最短路径是8,所以此时的最短路径是9,9<13所以这里应该更新最短路径为9

这里最短路径算是更新完了。
算法思路
由于这里我们涉及到最短路径,所以应该开辟一个dist数组,我们来想一想一个dist数组是否能解决问题,很显然是不能的,我们还需要一个数组,记录当前最短路径的前一个顶点的下标,在遍历的时候我们可以索引每一个顶点了。
代码展示:
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{//获取起点的下标size_t srci = GetVertexIndex(src);//确定节点的数量size_t n = _vertexs.size();dist.resize(n, MAX_W);pPath.resize(n, MAX_W);//自己到自己的距离是0dist[srci] = 0;//自己的前一个是自己pPath[srci] = srci;//已经确定最短路径的顶点的集合vector<bool> S(n, false);for(size_t j=0;j<n;j++){//选择最短路径顶点且不在s中更新其他路径int u = 0; //最小的那个点W min = MAX_W; //最小权值for (size_t i = 0;i < n;i++){if (S[i] == false && dist[i] < min){//选出最小的点u = i;//更新最小权值min = dist[i];}}//u被选出来S[u] = true;//松弛更新u连接出去的顶点v srci->u u->vfor (size_t v = 0;v < n;v++){//确定u连接出去的所有边if (S[v] == false && _matrix[u][v] != MAX_W && (dist[u] + _matrix[u][v]) < dist[v]){dist[v] = dist[u] + _matrix[u][v];//将v的父亲更新为upPath[v] = u;}}}
}
打印路径节点和最短路径:
//打印最短路径
void PrinrtShotPath(const V& src, vector<W>& dist, vector<int>& pPath)
{//获取起点的下标size_t srci = GetVertexIndex(src);//确定节点的数量size_t n = _vertexs.size();for (size_t i = 0;i < n;i++){if (i != srci){// 先找出i顶点的路径vector<int> path;size_t parenti = i;//先将自己存进去(自己不是原点先push进去)while (parenti != srci){path.push_back(parenti);parenti = pPath[parenti];}path.push_back(srci);//将路径逆置reverse(path.begin(), path.end());//打印出路径for (auto e : path){cout << _vertexs[e] << "->";}//打印最短路径cout << dist[i];cout << endl;}}
}
因为根据最后一个节点去推上一个节点,推完之后数组中的节点会是一个反着的路径,所以在打印的时候,应该先把数组逆置,逆置之后再进行打印。
总结
在本文中,我们深入探讨了迪杰斯特拉算法的原理与应用。作为一种经典的最短路径算法,迪杰斯特拉算法通过优先队列有效地解决了从单一源点到其他所有节点的最短路径问题。我们分析了其时间复杂度和空间复杂度,了解了在不同图形结构下的性能表现。
通过示例和实现,我们不仅掌握了算法的基本步骤,还体验了其在实际应用中的重要性。无论是在交通导航、网络路由还是各种优化问题中,迪杰斯特拉算法都发挥着不可或缺的作用。
希望本文能够帮助你更好地理解迪杰斯特拉算法,并为你在图论和算法领域的进一步学习打下坚实的基础。如果你有任何疑问或想法,欢迎在评论区与我交流!
相关文章:
【图论】迪杰特斯拉算法
文章目录 迪杰特斯拉算法主要特点基本思想算法步骤示例 实现迪杰斯特拉算法基本步骤算法思路 总结 迪杰特斯拉算法 迪杰特斯拉算法是由荷兰计算机科学家艾兹赫尔迪杰特斯拉(Edsger W. Dijkstra)在1956年提出的,用于解决单源最短路径问题的经…...
四、Python基础语法(数据类型转换)
数据类型转换就是将一种类型的数据转换为另外一种类型的数据,数据类型转换不会改变原数据,是产生一个新的数据。 变量 要转换为的类型(原数据) -> num int(28) 一.int()将其他类型转换为整型 1.整数类型的字符串转换为整型 num1 28 print(type…...
工业物联网的安全与隐私保护—SunIOT
【大家好,我是唐Sun,唐Sun的唐,唐Sun的Sun。一站式数智工厂解决方案服务商】 在当今数字化的时代,工业物联网(IIoT)正以前所未有的速度改变着工业生产的模式和效率。然而,随着工业物联网的广泛…...
二层网络和三层网络的理解与区别(包含通俗理解和归纳总结)
二层网络和三层网络是计算机网络中的两个不同层次,主要区别在于它们所处的OSI参考模型中的层次及其功能。 二层网络 (Layer 2 Network) 1.定义: 二层网络主要涉及数据链路层(Layer 2),这是OSI模型中的第二层。 它负…...
【C++】:lambda表达式的高级应用
欢迎来到 破晓的历程的 博客 ⛺️不负时光,不负己✈️ 引言 今天 我们来见见lambda表达式的高级用法 用法1:自定义删除器 有些类型的delete方法并不符合自身的析构方法,这时我们就需要自定义删除器。 unique_ptr<FILE> ptr1(fopen…...
详解正确创建好SpringBoot项目后但是找不到Maven的问题
目录 问题 解决步骤: 找到File->Project Structure... 设置SDK 设置SDKs 问题 刚刚在使用IDEA专业版创建好SpringBoot项目后,发现上方导航栏的运行按钮是灰色的,而且左侧导航栏的pom.xml的图标颜色也不是正常的,与此同时我…...
力扣203.移除链表元素
题目链接:203. 移除链表元素 - 力扣(LeetCode) 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val val 的节点,并返回 新的头节点 。 示例 1: 输入:head [1,2,6…...
UE4 材质学习笔记05(凹凸偏移和视差映射/扭曲着色器)
一.凹凸偏移和视差映射 1.偏移映射 这需要一个高度图并且它的分辨率很低,只有256*256,事实上,如果高度图的分辨率比较低并且有点模糊,效果反而会更好 然后将高度图输出到BumpOffset节点的height插槽中, 之后利用得到…...
网约班车升级手机端退票
背景 作为老古董程序员,不,应该叫互联网人员,因为我现在做的所有的事情,都是处于爱好,更多的时间是在和各行各业的朋友聊市场,聊需求,聊怎么通过IT互联网 改变实体行业的现状,准确的…...
【Vue】Vue 快速教程
Vue tutorial 参考:教程 | Vue.js (vuejs.org) 该教程需要前置知识:HTML, CSS, JavaScript 学习前置知识,你可以去 MDN Vue framework 是一个 JavaScript framework,以下简称 Vue,下面是它的特点 声明式渲染ÿ…...
SQLite数据库介绍
文章目录 SQLite常用接口 使用示例测试 SQLite SQLite是一个本地化的数据库,不需要客户端服务端什么的配置,主打就是轻量化方便化 他也不是一个独立的进程,而是可以根据应用程序的需求,可以进行静态或者动态的连接 而且他是直接存储在磁盘文件的,提供了简单易用的API接口 需…...
点击label 按钮起作用
要使点击 标签时能够触发与之关联的表单控件(如输入框、复选框或单选按钮)的作用,你需要正确地设置 标签的 for 属性,并确保该属性值与表单控件的 id 属性值相匹配。这样,当用户点击 标签时,与之关联的表…...
JPA、Hibernate、MyBatis三种ORM框架怎么选择
JPA(Java Persistence API)、Hibernate和MyBatis都是Java开发中常用的ORM(Object-Relational Mapping,对象关系映射)框架,它们提供了不同的方式来处理数据库交互。在选择这些框架时,需要考虑项目…...
【C++】map详解
📢博客主页:https://blog.csdn.net/2301_779549673 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📢本文由 JohnKi 原创,首发于 CSDN🙉 📢未来很长&#…...
力扣206.反转链表
题目链接:206. 反转链表 - 力扣(LeetCode) 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例 1: 输入:head [1,2,3,4,5]输出:[5,4,3,2,1] 示例 2: …...
如何查看服务器的带宽linux服务器
speedtest-cli ubuntu # 安装speedtest-cli sudo apt install speedtest-cli # 执行测试 speedtest --secure # 在其他博客可以看到使用以下的命令,但是我试了没用 speedtest-cli参考: https://ubuntu-mate.community/t/speedtest-cli-error/25722/2…...
云原生化 - 工具镜像(完整版)
在微服务和云原生环境中,容器化的目标之一是尽可能保持镜像小型化以提高启动速度和减少安全风险。然而,在实际操作中,有时候需要临时引入一些工具来进行调试、监控或问题排查。Kubernetes提供了临时容器(ephemeral containers)的功能,允许在不改变原始容器镜像的情况下,…...
leetcode68:文本左右对齐
给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可…...
Linux驱动学习——内核编译
1、从官网下载适合板子的Linux内核版本 选择什么版本的内核需要根据所使用的硬件平台而定,最好使用硬件厂商推荐使用的版本 https://www.kernel.org/pub/linux/kernel/ 2、将压缩包复制到Ubuntu内进行解压 sudo tar -xvf linux-2.6.32.2-mini2440-20150709.tgz 然…...
MES系统:制造业的智能大脑
引言 在当今快速变化的制造业环境中,企业面临着激烈的市场竞争和不断变化的客户需求。为了保持竞争力,制造企业必须提高生产效率、降低成本、缩短产品上市时间,并确保产品质量。MES(制造执行系统)作为一种先进的生产管…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
