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

数据结构-最短路径(Dijkstra算法与Floyd算法)

介绍

对于网图来说,最短路径是指两顶点之间经过的边上权值之和最少的路径,其路径上第一个点记为源点,最后一个为终点。

计算最短路径有两个经典算法,即迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法。

Dijkstra算法

这个算法是从一个给定的顶点出发,不断计算更新此顶点到目标顶点的最短路径

假如有这样一张网图

如果我们要求顶点0到顶点1的最短距离,那无疑是1。由于1还与2,3相连,所以我们也可以求出0->1->2的距离为1+2=3,0->1->3距离为1+4=5;

但如果求从顶点0到顶点2的最短距离,由于边上都有权值,5是大于3的,所以0到2的最短距离是3;

同时,因为2与3,4相连,我们可以求得由此路径的0->1->2->3=3+1=4,0->1->2->4的距离为4+4=7;而这条路径上0到3的距离要小于上述0->1->3那条,则目前0到3的最短距离更新为4

... ...以此类推,不断基于已经求出的中途的最短距离,来更新到目标顶点的最短路径,这就是这个算法的核心思想

具体代码实现

	typedef struct{int vex[max];//顶点数组int arc[max][max];//带权边长int numN,numE;//顶点数及边数
}Mgraph;//用邻接矩阵存储整张图
int p[max];//储存最短路径下标数组
int d[max];//储存到各点的最短路径权值和
void SPDijkstra(Mgraph g,int v0){//传入图与起始顶点int m;int final[max];//记录从v0到i顶点的最短路径for (int i=0;i<g.numN;i++){final[i]=0;//初始化未未知最短路径的状态d[i]=g.arc[v0][i];//将所有与v0有连线的加上权值p[i]=-1;//初始化路径数组为-1}d[v0]=0;//v0至v0距离为0final[v0]=1;//标记v0至v0不需要求路径int k;for (int i=1;i<g.numN;i++){//从v1开始找起m=INT_MAX;for (int j=0;j<g.numN;j++){if (!final[j]&&d[j]<m){m=d[j];k=j;//记录距v0最短的带权路径顶点}}final[k]=1;//标记此顶点//开始更新最短距离for (int j=0;j<g.numN;j++){if (!final[j]&&m+g.arc[k][j]<d[j]){d[j]=m+g.arc[k][j];//更新v0到j的最短路径p[j]=k;//v0到j顶点的最短路径前驱是k}}}
}

Floyd算法

还是以此图为例

弗洛伊德算法常用于求取所有顶点至所有顶点的最短路径,它利用动态规划的方法,将顶点至顶点间的最短路径记录在一个二维数组中

在带权的邻接矩阵中,arc[i][j]记录的为i j之间的距离,如例图中arc[0][2]=5

但如果找一个与两个顶点都相连的中间节点,如1,计算得出arc[0][1]+arc[1][2]=1+2=3,这个值是小于5的,这条路径的距离就可以更新到矩阵中代替5的位置

利用这种算法进行重复迭代,对于每一对顶点i,j,遍历所有的中间节点k,检查是否存在一条路径比当前更短,如果是则更新矩阵中的最短距离。这样就可以的出两个个顶点之间的最短路径与最短距离。

代码实现如下

int p[max][max];//p数组记录路径,方便后续输出最短路径
int d[max][max];//记录最短距离
void SPFloyd(Mgraph g){for (int i=0;i<g.numN;i++){for (int j=0;j<g.numN;j++){d[i][j]=g.arc[i][j];//初始化为邻接矩阵p[i][j]=j;//初始化路径数组}}for(int k=0;k<g.numN;k++){for (int i=0;i<g.numN;i++){for (int j=0;j<g.numN;j++){if(d[i][j]>d[i][k]+d[k][j]){d[i][j]=d[i][k]+d[k][j];//更新最短距离p[i][j]=p[i][k];//更新路径,即要到j的最短路径中,j之前一个顶点为k}}}}
}

相关文章:

数据结构-最短路径(Dijkstra算法与Floyd算法)

介绍 对于网图来说&#xff0c;最短路径是指两顶点之间经过的边上权值之和最少的路径&#xff0c;其路径上第一个点记为源点&#xff0c;最后一个为终点。 计算最短路径有两个经典算法&#xff0c;即迪杰斯特拉&#xff08;Dijkstra&#xff09;算法与弗洛伊德&#xff08;Fl…...

文献速递:GAN医学影像合成--联邦生成对抗网络基础医学图像合成中的后门攻击与防御

文献速递&#xff1a;GAN医学影像合成–联邦生成对抗网络基础医学图像合成中的后门攻击与防御 01 文献速递介绍 虽然深度学习在医疗保健研究中产生了显著影响&#xff0c;但其在医疗保健领域的影响无疑比在其他应用领域更慢、更有限。造成这种情况的一个重要原因是&#xff…...

Java实现自动化pdf打水印小项目 使用技术pdfbox、Documents4j

文章目录 前言源码获取一、需求说明二、 调研pdf处理工具word处理工具 三、技术栈选择四、功能实现实现效果详细功能介绍详细代码实现项目目录WordUtilsMain类实现部分&#xff1a;第一部分Main类实现部分&#xff1a;第二部分Main类实现部分&#xff1a;第三部分 资料获取 前言…...

hive load data未正确读取到日期

1.源数据CSV文件日期字段值&#xff1a; 2.hive DDL语句&#xff1a; CREATE EXTERNAL TABLE test.textfile_table1(id int COMMENT ????, name string COMMENT ??, gender string COMMENT ??, birthday date COMMENT ????,.......) ROW FORMAT SERDE org.apache.…...

C++ 遍历map的3中方法

方法1 #include <iostream> #include <string> #include <map> using namespace std;int main() {map<string, string> nameList {{"张三丰", "武当山"},{"张无忌", "光明顶"},{"张二蛋", "…...

redis 主从模式,sentinel 模式配置

编辑 sentinel.xml 和 redis.conf redis.conf 中核心是配置 bind 192.168.64.144 daemonize yes protected-mode no dbfilename redis-6379.rdb #默认dump.rdb replica-read-only yes # 自动2.6副本默认只读&#xff0c;也就是slave只有只读权限 replicationOf myapplicat…...

小型医院医疗设备管理系统|基于springboot小型医院医疗设备管理系统设计与实现(源码+数据库+文档)

小型医院医疗设备管理系统目录 目录 基于springboot小型医院医疗设备管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、职员信息管理 2、设备信息管理 3、库房信息管理 4、公告信息管理 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、…...

CSS学习(三)

目录&#xff1a; 1. CSS引入方式 1.1 三种样式表 1.2 内部样式表&#xff08;嵌入式引入&#xff09; 1.3 行内样式表&#xff08;内联样式表&#xff09; 1.4 外部样式表 1.5 总结 1. CSS引入方式 1.1 三种样式表 1.2 内部样式表&#xff08;嵌入式引入&#xff09; …...

CentOS7安装InfluxDB2简易教程

InfluxDB是一个开源的时间序列数据库&#xff0c;它专门用于处理大规模的时间序列数据。时间序列数据是在特定时间点上收集的数据&#xff0c;例如传感器数据、监控数据、应用程序日志等。 InfluxDB设计用于高效地存储、查询和分析大量的时间序列数据。它具有高性能、可扩展性和…...

数据库:信息存储与管理的关键

数据库&#xff1a;信息存储与管理的关键 数据库是现代信息系统中不可或缺的组成部分&#xff0c;它承担着存储、管理和检索数据的重要任务。本文将详细介绍数据库的定义、分类、作用以及特点。 1. 数据库的介绍 数据库是一个有组织的数据集合&#xff0c;用于存储和管理大量…...

极智芯 | 解读NVIDIA RTX5090 又是一波被禁售的节奏

欢迎关注我的公众号「极智视界」,获取我的更多技术分享 大家好,我是极智视界,本文分享一下 解读NVIDIA RTX5090 又是一波被禁售的节奏。 邀您加入我的知识星球「极智视界」,星球内有超多好玩的项目实战源码和资源下载,链接:https://t.zsxq.com/0aiNxERDq 按 NVIDIA GPU …...

rtt的io设备框架面向对象学习-硬件rtc设备

目录 1.硬件rtc设备基类2.硬件rtc设备基类的子类3.初始化/构造流程3.1设备驱动层3.2 设备驱动框架层3.3 设备io管理层 4.总结5.使用 硬件rtc和软件rtc设备是互斥的。因为它们的名字都叫"rtc"&#xff0c;在对象容器中不允许重名。 1.硬件rtc设备基类 此层处于设备驱…...

产品经理学习-产品运营《流程管理》

如何进行流程管理 信息可视化 甘特图-流程管理思维导图-方案讨论原型图-活动文档 明确责任制 分工明确&#xff0c;关键环境有主负责人通过时间倒推督促管理 沟通技巧 明确共同利益以结果激励做好信息同步 如何进行监控活动效果 监控活动的效果是要监控数据 活动每个环境的…...

压缩感知——革新数据采集的科学魔法

引言&#xff1a; 在数字时代&#xff0c;数据以及数据的收集和处理无处不在。压缩感知(Compressed Sensing, CS)是一种新兴的数学框架&#xff0c;它挑战了我们传统上对数据采集和压缩的看法&#xff0c;给医学图像、天文观测、环境监测等领域带来了颠覆性的影响。但到底什么…...

华为配置直连三层组网直接转发示例

华为配置直连三层组网直接转发示例 组网图形 图1 配置直连三层组网直接转发示例组网图 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件扩展阅读 业务需求 企业用户接入WLAN网络&#xff0c;以满足移动办公的最基本需求。且在覆盖区域内移动发生漫游时&#xff…...

MCAL知识点(二十八):TC275如何通过EB-Tresos配置实现硬件触发ADC同步采样(电机控制器三相电流同步采样)

目录 1、概述 2、实现目标 3、EB-Tresos配置 3.1、AdcGeneral 3.2、AdcGlobInputClass 3.3、AdcHwUnit_X...

proteus8.15图文安装教程

proteus8.15版本可以用STM32系列单片机来进行仿真设计&#xff0c;比7.8版本方便多了&#xff0c;有需要的朋友们可以在公众号后台回复 proteus8.15 获取软件包。 1、下载好软件包&#xff0c;解压如下&#xff0c;右键proteus8.15.sp1以管理员身份运行。 2、第一次安装&#x…...

ACP科普:敏捷开发之kanban

Q1: Kanban是什么&#xff1f; A1:敏捷开发中的Kanban是一种项目管理方法&#xff0c;其核心理念是通过可视化管理来提高生产效率和任务交付速度。Kanban来自日本&#xff0c;意为“看板”&#xff0c;最初是由丰田汽车公司引入生产线上的生产控制系统&#xff0c;后来被引入到…...

代理模式(Proxy模式)

所谓的代理&#xff0c;就是一个人或者一个机构代替另一个人或者另一个机构去做一些事情&#xff08;类似于中介或者代理商&#xff09;。 代理的种类 远程代理&#xff1a;为一个位于不同的地址空间的对象提供一个局域代表对象。 虚拟代理&#xff1a;根据需要创建一个资源消…...

Android使用shape定义带渐变色的背景

在drawable目录下创建文件bg_gradient.xml 文件内的内容如下&#xff1a; <?xml version"1.0" encoding"utf-8"?> <shape android:shape"rectangle" xmlns:android"http://schemas.android.com/apk/res/android"> <…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...