数据结构 —— Dijkstra算法

数据结构 —— Dijkstra算法

  • Dijkstra算法
  • 划分集合
  • 模拟过程
  • 打印路径

在上次的博客中,我们解决了使用最小的边让各个顶点连通(最小生成树
在这里插入图片描述这次我们要解决的问题是现在有一个图,我们要找到一条路,使得从一个顶点到另一个顶点路径权值之和最小(比如:找到从小潮到胖迪最短的一条路径):
在这里插入图片描述
我们可以看出来,小潮->小傲->胖迪这条路径是最短的。
在这里插入图片描述
而我们今天学的算法,Dijkstra,就是完成这样的工作的:

Dijkstra算法

Dijkstra算法是一种用于寻找图中两个节点之间的最短路径的算法,由荷兰计算机科学家Edsger W. Dijkstra于1956年发明。该算法的基本思想是使用贪心策略,从起始节点开始,逐步扩展到距离它最近的未访问过的节点,直到目标节点被访问。

以下是Dijkstra算法的基本步骤:

  1. 初始化将起点到所有其他节点的距离设为无穷大(表示还未计算),除了起点到自身的距离为0。创建一个空的已访问节点集合和一个包含所有节点的未访问节点集合。
  1. 从未访问节点集合中选择距离起点最近的节点,将其标记为已访问,并更新其邻接节点的距离如果某个邻接节点的距离通过当前节点更短,则更新该邻接节点的距离
  1. 重复步骤2,直到找到目标节点或未访问节点集合为空。
  1. 如果找到了目标节点,则返回从起点到目标节点的最短路径;否则,说明起点和目标节点之间不存在路径。

需要注意的是,Dijkstra算法只适用于没有负权重边的图,因为负权重边会导致算法无法正确地确定最短路径。此外,Dijkstra算法的时间复杂度为O(ElogV),其中E表示边的数量,V表示节点的数量。在实际应用中,可以使用优先队列等数据结构来优化算法的时间复杂度。

我们将上面的图改造复杂一点,这样可以看出Dijkstra算法的高效:
在这里插入图片描述

void TestGraph2(){string a[] = {"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));g1.AddEdge("小潮", "小傲", 30);g1.AddEdge("小潮", "高斯", 83);g1.AddEdge("小潮", "海皇", 34);g1.AddEdge("胖迪", "海皇", 78);g1.AddEdge("胖迪", "小傲", 76);g1.AddEdge("小杨", "皖皖", 54);g1.AddEdge("小杨", "高斯", 48);g1.AddEdge("高斯", "皖皖", 55);g1.AddEdge("胖迪", "高斯", 70);g1.AddEdge("小傲", "海皇", 3);g1.Print();cout << endl;}

在这里插入图片描述

划分集合

Dijkstra算法中,提到我们要划分集合一个是访问过的集合,一个是没有被访问过的集合,假设我们从小潮开始:
在这里插入图片描述
我们可以用一个bool的数组,访问过了的标记为true,没有为false。
在这里插入图片描述假设我们要从小潮到胖迪,我们要计算路径之和,我们还需要一个数组存放到各个顶点边的权值:

在这里插入图片描述同时,如果我们想打印路径出来,我们还要一个数组存放路径(这里有点像并查集里面的操作)
在这里插入图片描述

模拟过程

假设我们从小潮开始,各个数组情况如下:
在这里插入图片描述

现在,扫描跟小潮相连的边,最小的权值相关结点标记:
在这里插入图片描述

现在我们从小傲出发,发现海皇近,跳到海皇,发现总路径之和为33,比原来34小,故更新,并标记:

在这里插入图片描述
我们代码实现一下:

    void Dijkstra(const V& srci, vector<W>& dest, vector<int>& parentPath ){// 将源节点转换为其在顶点列表中的索引int srcIndex = FindSrci(srci);// 初始化parentPath向量,用于记录最短路径上的前驱节点,初始值为-1表示未访问parentPath.resize(_vertex.size(), -1);// 初始化dest向量,用于记录从源节点到每个节点的最小距离,初始值为最大权重MAX_Wdest.resize(_vertex.size(), MAX_W);// 给源节点赋值为0,表示从源节点到自身距离为0dest[srcIndex] = W();// 初始化一个布尔型向量,用于记录每个节点是否已被访问,初始值为falsevector<bool> isVisted;isVisted.resize(_vertex.size(), false);// 主循环,迭代次数为顶点数for (size_t i = 0; i < _vertex.size(); i++){// 初始化最小距离为最大权重MAX_WW min = MAX_W;size_t u = srcIndex;// 寻找未被访问且具有最小dest值的节点ufor (size_t j = 0; j < _vertex.size(); j++){if (isVisted[j] == false && dest[j] < min){min = dest[j];u = j;}}// 标记节点u为已访问isVisted[u] = true;// 对节点u的所有邻居进行松弛操作for (size_t i = 0; i < _vertex.size(); i++){// 只处理未被访问的邻居,并且存在从u到i的边(_matrix[u][i] != MAX_W)if (isVisted[i] == false && _matrix[u][i] != MAX_W&& dest[u] + _matrix[u][i] < dest[i]){// 更新从源节点到节点i的最小距离dest[i] = dest[u] + _matrix[u][i];// 更新节点i的前驱节点为uparentPath[i] = u;}}}}

在这里插入图片描述

打印路径

打印路径记得一点,最后我们要逆置一下:

    // 打印从源节点到所有其他节点的最短路径void PrintShortestPath(const V& src, const vector<W>& dist, const vector<int>& parentPath){// 将源节点转换为其在顶点列表中的索引size_t srcIndex = FindSrci(src);// 遍历所有顶点for (size_t i = 0; i < _vertex.size(); i++){// 跳过源节点本身if (i == srcIndex)continue;// 创建一个vector,用于存储从目标节点到源节点的路径vector<int> path;// 当前处理的节点初始化为目标节点size_t current = i;// 从目标节点出发,回溯到源节点,构建路径while (current != srcIndex){// 将当前节点添加到路径vector中path.push_back(current);// 将当前节点设置为其前驱节点,继续回溯current = parentPath[current];}// 最后将源节点添加到路径vector中path.push_back(srcIndex);// 翻转路径vector,使得路径顺序从源节点到目标节点reverse(path.begin(), path.end());// 输出路径和对应的最短距离for (auto node : path){// 输出路径中的每个节点cout << _vertex[node] << "->";}// 输出从源节点到目标节点的最短距离cout << dist[i] << endl;}}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/372772.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】网络新兵连

欢迎来到 破晓的历程的 博客 ⛺️不负时光&#xff0c;不负己✈️ 引言 在上一篇博客中&#xff0c;我们简单的介绍了一些Linux网络一些比较基本的概念。本篇博客我们将开始正式学习Linux网络套接字的内容&#xff0c;那么我们开始吧&#xff01; 1.网络中的地址管理 大家一…

2024年 春秋杯 网络安全联赛夏季赛 Web方向 题解WirteUp 部分

brother 题目描述&#xff1a;web哥&#xff0c;打点容易提权难。 打点就是最简单的SSTI。 执行下find / -user root -perm -4000 -print 2>/dev/null找一下具备suid权限的命令 /usr/lib/dbus-1.0/dbus-daemon-launch-helper /usr/bin/chsh /usr/bin/gpasswd /usr/bin/n…

Java面试八股之MySQL中的锁及其作用

MySQL中的锁及其作用 MySQL中的锁分类 全局锁&#xff08;Global Lock&#xff09;&#xff1a; 描述&#xff1a;对整个数据库实例加锁&#xff0c;最常见的是FLUSH TABLES WITH READ LOCK命令&#xff0c;主要用于全库备份等场景&#xff0c;阻止所有对表的写入操作。 作…

7月开刷880题,30天搞定必刷重点‼️

李林880一定要在暑假期间给吃透 马上就要刷家了&#xff0c;教大家一个方法&#xff0c;30天吃透880题&#xff0c;正确了90%&#xff01; 25版880题变化并不大&#xff0c;25版的主要改动是在去年的李6李4模拟题中挑选了约40道题&#xff0c;加入到今年的新版本中。 具体而…

PDF内存如何变小,PDF内存压缩,PDF内存变小怎么调整

在数字化时代&#xff0c;pdf已成为工作、学习和生活中不可或缺的文件格式。它以其跨平台兼容性和安全性受到广大用户的喜爱。然而&#xff0c;随着pdf文件中嵌入的图片、图形和文本内容的增多&#xff0c;文件大小往往会变得相当可观&#xff0c;给文件的传输和存储带来一定的…

python采集阿里巴巴历年员工人数统计报告

数据为2012到2022财年阿里巴巴每年的全职员工数量。截止2022年3月31日&#xff0c;阿里巴巴共有全职员工254941人&#xff0c;比上年增长3479人。 数据来源于阿里巴巴20-F和F-1文件 按阿里巴巴财政年度进行统计&#xff0c;阿里巴巴财年结束日期为每年3月31日 为全职员工人数 阿…

探索横河AQ6370E系列光谱仪隐藏功能!---高级标记功能!

横河AQ6370E系列光谱仪的这款光谱仪的传统功能中&#xff0c;其实还隐藏了一个特别实用的功能——高级标记功能&#xff01;前所未有的方式解析数据与测量信号&#xff0c;不仅带来了全新的测试体验&#xff0c;还提升了测量速度&#xff0c;那么这个功能怎么找到呢&#xff0c…

绝区陆--大语言模型的幻觉问题是如何推动科学创新

介绍 大型语言模型 (LLM)&#xff08;例如 GPT-4、LLaMA-2、PaLM-2、Claude-2 等&#xff09;已展示出为各种应用生成类似人类文本的出色能力。然而&#xff0c;LLM 的一个鲜为人知的方面是它们倾向于“产生幻觉”或生成不正确或没有根据的事实陈述。我不认为这仅仅是一个限制…

电脑硬盘分区的基本步骤(2个实用的硬盘分区方法)

在现代计算机中&#xff0c;硬盘分区是非常重要的一步。无论是新硬盘的初始化&#xff0c;还是重新组织现有硬盘&#xff0c;分区都是必不可少的操作。本文将详细介绍电脑硬盘分区的基本步骤&#xff0c;帮助您更好地管理和利用硬盘空间。 文章开始&#xff0c;我们先简单说一…

python——list

在Python中&#xff0c;list是一种非常灵活的数据结构&#xff0c;可以用来存储一系列的元素。这些元素可以是任何类型&#xff0c;包括数字、字符串、其他列表等&#xff0c;并且它们不需要是同一种类型。 列表特征&#xff1a; 以下是一些关于Python列表的基本操作&#xff…

Intellj idea无法启动

个人电脑上安装的是2024.01版本的intellj idea作为开发工具&#xff0c;引入了javaagent作为工具包 但是在一次invaliad cache操作后&#xff0c;intellj idea就无法启动了&#xff0c;双击无响应。 重装了idea后也无效&#xff08;这个是有原因的&#xff0c;下面会讲&#…

仕考网:公务员体检对视力有要求吗?

公务员招聘过程中的体检标准对视力有具体要求&#xff0c;根据不同的岗位职责有所差异。通常情况下&#xff0c;如果申请者双眼经过矫正后视力均低于4.8(小数视力0.6)&#xff0c;则会被视为不合格。 对于某些特殊岗位&#xff0c;如J察等&#xff0c;单侧裸眼视力若低于4.8也…

Vue学习笔记-自定义组件使用v-model

拆解实现 父组件 <template><div></div><Son :name"name" inputChange"inputChange"></Son>{{ name }} </template><script setup> import {ref} from vue import Son from ./son2.vueconst nameref("张…

为什么需要重写equals和如何重写equals

首先先看Java中的 &#xff0c;比较的两个对象的地址值。 如果是基本数据类型&#xff0c;那么就是比较的是值。 如果是引用数据类型&#xff0c;比较的就是地址. object类中的equals方法也是用的&#xff1b; 所以要比较两个对象的大小&#xff0c;去调用默认的equals方法…

C#桌面应用开发:番茄定时器

C#桌面应用开发&#xff1a;番茄定时器 1、环境搭建和工程创建&#xff1a; 步骤一&#xff1a;安装visual studio2022 步骤二&#xff1a;新建工程 2、制作窗体部件 *踩过的坑&#xff1a; &#xff08;1&#xff09;找不到工具箱控件&#xff0c;现象如下&#xff1a;…

虚幻引擎在建筑和房地产中的五大颠覆性应用:探索新时代的优势

最初&#xff0c;虚幻引擎作为一个强大的游戏开发工具出现。它不断推动虚拟环境的可能性边界。正因如此&#xff0c;它的使用自然而然地超越了游戏开发&#xff0c;涵盖了包括建筑工程在内的其他行业。那么&#xff0c;在建筑和房地产领域使用虚幻引擎有哪些好处呢&#xff1f;…

代码随想录day36

题目一 上边、左边初始化为1 采用求和进行dp运算 class Solution(object):def uniquePaths(self, m, n):""":type m: int:type n: int:rtype: int"""dp [[0]*n for _ in range(m)]for i in range(m):dp[i][0] 1for j in range(n):dp[0][j] 1…

逻辑回归模型(非回归问题,而是解决二分类问题)

目录&#xff1a; 一、Sigmoid激活函数&#xff1a;二、逻辑回归介绍&#xff1a;三、决策边界四、逻辑回归模型训练过程&#xff1a;1.训练目标&#xff1a;2.梯度下降调整参数&#xff1a; 一、Sigmoid激活函数&#xff1a; Sigmoid函数是构建逻辑回归模型的重要激活函数&am…

mysql查询语句执行流程

流程图 连接器&#xff1a;建立连接&#xff0c;管理连接、校验用户身份&#xff1b;查询缓存&#xff1a;查询语句如果命中查询缓存则直接返回&#xff0c;否则继续往下执行。MySQL 8.0 已删除该模块&#xff1b;解析 SQL&#xff0c;通过解析器对 SQL 查询语句进行词法分析、…

充电宝哪个牌子公认质量好?哪家充电宝好用?4款口碑好充电宝

在如今这个电子设备不离手的时代&#xff0c;充电宝成为了我们生活中的必备品。然而&#xff0c;面对市场上琳琅满目的充电宝品牌和型号&#xff0c;选择一款质量可靠、性能出色的充电宝并非易事。大家都在问&#xff1a;充电宝哪个牌子公认质量好&#xff1f;哪家充电宝好用&a…