当前位置: 首页 > 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"> <…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

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

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

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...