数据结构 —— 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_W
        dest.resize(_vertex.size(), MAX_W);

        // 给源节点赋值为0,表示从源节点到自身距离为0
        dest[srcIndex] = W();

        // 初始化一个布尔型向量,用于记录每个节点是否已被访问,初始值为false
        vector<bool> isVisted;
        isVisted.resize(_vertex.size(), false);

        // 主循环,迭代次数为顶点数
        for (size_t i = 0; i < _vertex.size(); i++)
        {
            // 初始化最小距离为最大权重MAX_W
            W min = MAX_W;
            size_t u = srcIndex;

            // 寻找未被访问且具有最小dest值的节点u
            for (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的前驱节点为u
                    parentPath[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;
        }
    }

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

前端JS特效第26波:jQuery日期时间选择器插件

jQuery日期时间选择器插件&#xff0c;先来看看效果&#xff1a; 部分核心的代码如下&#xff1a; <!DOCTYPE html> <html> <head lang"zh-CN"> <meta charset"UTF-8"> <title>jQuery日期时间选择器插件 - PHP中文网</t…

UI自动化测试是什么?什么项目适合做UI自动化测试

1. 页面对象设计模式的优势 (1) 创建可以跨多个测试用例共享的代码 (2) 减少代码的重复性 (3) 如果界面需要维护&#xff0c;只需要修改一个地方&#xff0c;修改以及维护的成本减少 2. 每个目录结构表达的意思 (1) Base:基础层&#xff0c;是用来编写定位元素 (2) Commo…

PL/SQL安装+汉化教程

PL/SQL安装教程 一、安装&#xff1a; 登陆官网&#xff1a;PL/SQL Developer - Allround Automations下载 下载PL/SQL稳定版本12.0.7 根据自己计算机版本安装相适配的版本。我这里安装X64-bit版本 进行安装&#xff1a; 根据情况去更改安装&#xff0c;我这里全部下一步…

【从零到一,如何搭建本地AI大模型】

摘要: 本文主要记录这一段时间对本地大模型搭建的心得。 作为一个资深程序员,在AI席卷全球的时候,深深感觉到了一丝危机感,不禁有一个想法不断在脑海闪现:我会不会真的哪一天被AI给取代了? 从哪入手 程序员出生的我,掌握了很多语言,从前端到数据库,再到运维,基本都…

Java基础-组件及事件处理(上)

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 Swing 概述 MVC 架构 Swing 特点 控件 SWING UI 元素 JFrame SWING 容器 说明 常用方法 示例&a…

为什么选择虚拟艺术设计展览?艺术家应知的五个关键好处

随着技术的进步&#xff0c;虚拟艺术设计展览成为了展示艺术作品的重要途径。它不仅为艺术家们提供了新的展示平台&#xff0c;还打破了传统展览的局限。 1、扩大观众范围&#xff1a;打破地理限制 虚拟艺术设计展览能够打破地理限制&#xff0c;使得全球观众可以随时随地访问…

Androidstudio开发,天气预报APP

1.项目功能思维导图 2. 项目涉及到的技术点 数据来源&#xff1a;和风天气API使用okhttp网络请求框架获取api数据使用gson库解析json数据使用RecyclerViewadapter实现未来7天列表展示和天气指数使用PopupMenu 实现弹出选项框使用动画定时器实现欢迎页倒计时和logo动画使用Text…

《梦醒蝶飞:释放Excel函数与公式的力量》10.2 COMPLEX函数

第二节 10.2 COMPLEX函数 10.2.1函数简介 COMPLEX函数是Excel中的一个工程函数&#xff0c;用于将实部和虚部组合成一个复数。复数广泛应用于工程、电气、物理等领域&#xff0c;COMPLEX函数提供了方便的复数表示和计算方法。 10.2.2语法&#xff1a; COMPLEX(real_num, i_…

SpringSecurity-SpirngBoot-方法级授权(SpringSecurity6.3新特性)(四)

SpringSecurity-SpirngBoot-方法级授权&#xff08;SpringSecurity6.3新特性&#xff09;&#xff08;四&#xff09; 本章使用SpringSecurity6.3新特性实现数据级别的鉴权&#xff0c;主要的目的是实现不同权限的用户查询同一个方法&#xff0c;限制一些内容只能拥有特定权限…

自定义@AnonymousAccess注解

一.目的&#xff1a; 自定义AnonymousAccess注解&#xff0c;可以直接在controller上添加该注解使请求绕过权限验证进行匿名访问&#xff0c;便于快速调用调试以及部分不需要进行安全验证的接口。而不是每次都需要去SecurityConfig文件中进行修改。 二.流程&#xff1a; 三.实…

阿里MotionShop——AI视频工具:一键替换视频人物为3D虚拟角色~

近期AI相关的新奇应用层出不穷&#xff0c;今天小元老师要给大家安利一个由阿里巴巴研发的AI视频生成技术——MotionShop&#xff01; 1、一键替换3D虚拟角色 MotionShop通过视频处理、角色检测、背景修复等多重步骤&#xff0c;能够将视频中的人物角色&#xff0c;一键转换成…

Pytorch(笔记7损失函数类型)

前言 损失函数&#xff08;Loss Function&#xff09;&#xff1a;是定义在单个样本上的&#xff0c;是指一个样本的误差&#xff0c;度量模型一次预测的好坏。 代价函数&#xff08;Cost Function&#xff09;成本函数经验风险&#xff1a;是定义在整个训练集上的&#xff0c…

文件防止拷贝如何实现?这些攻略给你了

在信息爆炸的时代&#xff0c;数据安全成为企业和个人不可忽视的重要环节。文件的非法拷贝不仅可能侵犯知识产权&#xff0c;还可能导致敏感信息的泄露&#xff0c;进而引发严重的后果。 因此&#xff0c;了解并掌握文件防止拷贝的方法和技术至关重要。本文将详细介绍几种常见…

压测jmeter 插件 之 tps和响应时间图

1. 背景 进行压测ing 2. 需要插件 TPS 和 响应时间 3. 插件 在 选项-最下面-plugins Manager 在 Available Plugins 中 搜索 &#xff1a;jpgc - Standard Set 重启安装就好啦

12--RabbitMQ消息队列

前言&#xff1a;前面一章内容太多&#xff0c;写了kafka&#xff0c;这里就写一下同类产品rabbitmq&#xff0c;rabbitmq内容较少&#xff0c;正好用来过度一下&#xff0c;概念还是会用一些例子来说明&#xff0c;实际部署的内容会放在概念之后。 1、基础概念 1.1、MQ消息队…

年化15.73%:创业板指数布林带突破Backtrader策略(代码+数据)

原创文章第582篇&#xff0c;专注“AI量化投资、世界运行的规律、个人成长与财富自由"。 昨天咱们使用backtrader&#xff0c;重写了创业板动量趋势择时&#xff1a;年化19.2%&#xff1a;backtraderquantstats实现创业板动量择时(代码数据) 今天咱们换一个通道指标&#…

计算机视觉研究方向初学习,计算机视觉都有什么方向??!到底是干什么的?!

计算机视觉研究方向初学习&#xff0c;计算机视觉都有什么方向&#xff1f;&#xff1f;&#xff01;到底是干什么的&#xff1f;&#xff01; 语义分割图像分类目标检测和定位实例分割、全景分割物体跟踪姿态估计人脸识别人体识别图像增强风格迁移图像生成视觉问答视频分析光学…

C++视觉开发 七.模板匹配

模板匹配是一种基于图像处理的技术&#xff0c;用于在目标图像中寻找与给定模板图像最相似的部分。通过设定的模板&#xff0c;将目标图像与模板图像比较&#xff0c;计算其相似度&#xff0c;实现对目标图像的判断。 目录 一.手写数字识别 重要函数&#xff1a; 1.cv::glob…

【已解决】腾讯云安装了redis,但是本地访问不到,连接不上

汇总了我踩过的所有问题。 查看配置文件redis.conf 1、把bind 127.0.0.1给注释掉&#xff08;前面加个#就是&#xff09;或者改成bind 0.0.0.0&#xff0c;因为刚下载时它是默认只让本地访问。&#xff08;linux查找文档里的内容可以输入/后面加需要匹配的内容&#xff0c;然后…

FAO(脂肪酸β-氧化,Fatty acid beta-oxidation)应用实例

一、FAOBlue及其香豆素衍生物的吸收光谱和荧光光谱 在PBS缓冲液&#xff08;pH 7.4&#xff09;中&#xff0c;FAO代谢后释放的FAOBlue和香豆素衍生物的吸收光谱&#xff08;左&#xff09;、荧光光谱&#xff08;右&#xff09;。 FAOBlue经过FAO转化为香豆素衍生物后&#…