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

多源最短路径算法–Floyd算法

多源最短路径算法–Floyd算法

Floyd算法是为了求出每一对顶点之间的最短路径

它使用了动态规划的思想,将问题的求解分为了多个阶段

先来个例子,这是个有向图

image-20240603204954672

Floyd算法的运行需要两个矩阵

最短路径矩阵

从当前这个状态看各顶点间的最短路径长度

例如初始状态

image-20240603205335892

可以看出这是该有向图的邻接矩阵

顶点之间中转点矩阵

初始状态都没有中转点

image-20240603205552462

引入中转点

A(k-1)代表引入顶点k-1时,各个顶点的最短路径状态

path(k-1)代表引入顶点k-1后,各个顶点的最短路径需要经过哪个结点

image-20240603205810674

判断顶点i到顶点j,如果经过顶点k,是否会更短?

如果更短,改变A(k-1)数组中i结点到j结点的最短路径,同时更改path(k)数组,表明经过顶点k,顶点i到顶点j路径更短

  1. 允许在V0中转,计算出当前的最短路径

顶点2到顶点1

image-20240603211244772

image-20240603212147797

可以看到原来顶点2到顶点1是没有路径的,通过V0之后,最短路径变为11,那么更新A(0)数组,A(0)数组代表引入V0之后个顶点之间的最短路径,同是更新path(0)数组,代表V2到V1经过了V0

image-20240603211526708

image-20240603211546106

  1. 允许在V0,V1中转,计算出当前的最短路径

顶点0到顶点2

image-20240603211954682

image-20240603212231260

可以看到原来顶点0到顶点2的距离是13,通过V1之后,最短路径变为10,那么更新A(1)数组,A(1)数组代表引入V1之后个顶点之间的最短路径,同是更新path(1)数组,代表V0到V2经过了V1

image-20240603212030290

image-20240603212106992

  1. 允许在V0,V1,V2中转,计算出当前的最短路径

顶点1到顶点0

image-20240603212721776

image-20240603212106992

可以看到原来顶点1到顶点0的距离是10,通过V1之后,最短路径变为9,那么更新A(2)数组,A(2)数组代表引入V2之后个顶点之间的最短路径,同是更新path(2)数组,代表V1到V0经过了V2

image-20240603212902031

  1. 最终结果

image-20240603212954609

  1. 核心代码

image-20240603213039178

再看一个新的例子

image-20240603213128063

  1. 允许在V0中转,k=0

image-20240603213256094

所有结点之间都不能通过V0获得更短的路径,故不更新A(0)数组和path(0)数组

image-20240603213354113

  1. 允许在V0,V1中转,k=1

image-20240603213500090

image-20240603213531346

V2到V3和V2到V4经过V0,V1中转有更短的路径,故更新A(1)数组和path(1)数组

image-20240603213702181

  1. 允许在V0,V1,V2中转,k=2

image-20240603213912757

image-20240603213941700

V0到V1,V0到V3,V0到V4经过V0,V1,V2中转有更短的路径,故更新A(2)数组和path(2)数组

image-20240603214117232

  1. 允许在V0,V1,V2,V3中转,k=3

image-20240603214152875

image-20240603214208631

V0到V4,V1到V4,V2到V4经过V0,V1,V2,V3中转有更短的路径,故更新A(3)数组和path(3)数组

image-20240603214309276

  1. 允许在V0,V1,V2,V3,V4中转,k=4

image-20240603214352782

所有结点之间都不能通过V4获得更短的路径,故不更新A(4)数组和path(4)数组

image-20240603214458711

注意

  1. Floyd算法不能解决带有“负权回路”的图,这种图可能没有最短路径

相关文章:

多源最短路径算法–Floyd算法

多源最短路径算法–Floyd算法 Floyd算法是为了求出每一对顶点之间的最短路径 它使用了动态规划的思想,将问题的求解分为了多个阶段 先来个例子,这是个有向图 Floyd算法的运行需要两个矩阵 最短路径矩阵 从当前这个状态看各顶点间的最短路径长度 例…...

使用Redis缓存实现短信登录逻辑,手机验证码缓存,用户信息缓存

引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency> 加配置 spring:redis:host: 127.0.0.1 #redis地址port: 6379 #端口password: 123456 #密码…...

探索未来制造,BFT Robotics引领潮流

“买机器人&#xff0c;上BFT” 在这个快速变化的时代&#xff0c;创新和效率是企业发展的关键。BFT Robotics&#xff0c;作为您值得信赖的合作伙伴&#xff0c;专注于为您提供一站式的机器人采购和自动化解决方案。 产品系列&#xff1a; 协作机器人&#xff1a;安全、灵活、…...

数组中的第K个最大元素 ---- 分治-快排

题目链接 题目: 分析: 这道题很明显是一个top-K问题, 我们很容易想到用堆排序来解决, 堆排序的时间复杂度是O(N*logN), 不符合题意, 所以我们可以用另一种方法:快速选择算法, 他的时间复杂度为O(N)快速选择算法, 其实是基于快排, 进行修改而成, 我们还是使用将"将数组分…...

函数或变量 ‘tfrstft‘ 无法识别

参考博客 Matlab时频工具箱tftb下载及安装_tftb工具箱-CSDN博客 解决。...

在推荐四款软件卸载工具,让流氓软件无处遁形

Revo Uninstaller Revo Uninstaller是一款电脑软件、浏览器插件卸载软件&#xff0c;目前已经有了17年的历史了。可以扫描所有window用户卸载软件后的残留物&#xff0c;并及时清理&#xff0c;避免占用电脑空间。 Revo Uninstaller可以通过命令行卸载软件&#xff0c;可以快速…...

「前端+鸿蒙」核心技术HTML5+CSS3(十一)

1、CSS3 简介 CSS3 是层叠样式表的最新标准,它引入了许多新特性来增强网页的表现力。CSS3 不仅增强了现有CSS属性的功能,还引入了新的布局方式、动画、渐变、阴影、边框效果等。 2、CSS3 长度单位 CSS3 引入了一些新的单位,包括但不限于: vw(视口宽度的百分比)vh(视口…...

【高频】如何优化一个SQL语句

使用合适的索引&#xff1a;确保查询中涉及的字段上有合适的索引&#xff0c;避免全表扫描。可以通过 EXPLAIN 命令来查看查询执行计划&#xff0c;判断是否使用了索引。 避免使用通配符查询&#xff1a;尽量避免在查询条件中使用通配符&#xff08;如 %&#xff09;&#xff…...

Oracle EBS AP发票创建会计科目提示:APP-SQLAP-10710:无法联机创建会计分录

系统版本 RDBMS : 12.1.0.2.0 Oracle Applications : 12.2.6 问题症状: 提交“创建会计科目”请求提示错误信息如下: APP-SQLAP-10710:无法联机创建会计分录。 请提交应付款管理系统会计流程,而不要为此事务处理创建会计分录解决方法 数据修复SQL脚本: UPDATE ap_invoi…...

T-Pot多功能蜜罐实践@debian12@FreeBSD

T-Pot介绍 T-Pot是一个集所有功能于一身的、可选择分布式的多构架&#xff08;amd64&#xff0c;arm64&#xff09;蜜罐平台&#xff0c;支持20多个蜜罐和很多可视化选项&#xff0c;使用弹性堆栈、动画实时攻击地图和许多安全工具来进一步改善欺骗体验。GitHub - telekom-sec…...

Sed流编辑器总结

sed 是 Unix 和 Linux 系统中的一个强大的流编辑器。它用于对文本进行基本的修改和处理。以下是关于 sed 的详细解说&#xff0c;包括其基本语法&#xff0c;常见用法和一些高级用法。 基本语法 sed [选项] 命令 输入文件常见选项 -e&#xff1a;指定要执行的 sed 命令。-f&a…...

智合同丨AIGC如何助力合同智能应用

#AIGC #合同智能应用 #智合同 AIGC&#xff0c;即人工智能生成内容技术&#xff08;Artificial Intelligence Generated Content&#xff09;&#xff0c;近期在各个领域发展可谓是如火如荼&#xff0c;那么它在合同智能应用方面可以提供哪些助力&#xff1f; 让我们和智合…...

CSRF 令牌的生成过程和检查过程

在 Django 中,CSRF 令牌的生成和检查过程是通过 Django 的 CSRF 中间件 (CsrfViewMiddleware) 和模板标签 ({% csrf_token %}) 自动处理的。以下是详细的生成和检查过程: CSRF 令牌的生成过程 用户访问页面: 当用户第一次访问页面时,Django 会为用户创建一个会话。如果用户…...

计算机网络学习记录 网络层 Day4(下)

计算机网络学习记录 网络层 Day4 &#xff08;下&#xff09; 你好,我是Qiuner. 为记录自己编程学习过程和帮助别人少走弯路而写博客 这是我的 github https://github.com/Qiuner ⭐️ ​ gitee https://gitee.com/Qiuner &#x1f339; 如果本篇文章帮到了你 不妨点个赞吧~ 我…...

3、前端本地环境搭建

前端本地环境搭建 安装node [node下载地址] https://nodejs.org/en/download/prebuilt-installer 选择LTS的版本进行下载 下载后直接双击点击&#xff0c;选择自己想要安装到的目录一直点下一步即可&#xff08;建议不要安装到c盘&#xff09; 安装完成后配置环境变量&am…...

Python爬取城市空气质量数据

Python爬取城市空气质量数据 一、思路分析1、寻找数据接口2、发送请求3、解析数据4、保存数据二、完整代码一、思路分析 目标数据所在的网站是天气后报网站,网址为:www.tianqihoubao.com,需要采集武汉市近十年每天的空气质量数据。先看一下爬取后的数据情况: 1、寻找数据…...

【MyBatisPlus条件构造器】

文章目录 什么是条件构造器&#xff1f;使用步骤1. 引入 MyBatisPlus 依赖2. 创建实体类3. 使用条件构造器查询4. 执行查询 示例代码 什么是条件构造器&#xff1f; 条件构造器是 MyBatisPlus 提供的一种灵活的查询条件设置方式&#xff0c;它可以帮助开发者构建复杂的查询条件…...

容器多机部署eureka及相关集群服务出现 Request execution failed with message: AuthScheme is null

预期部署方案&#xff1a;两个eureka三个相关应用 注册时应用出现&#xff1a;Request execution failed with message: Cannot invoke “Object.getClass()” because “authScheme” is null&#xff0c;一开始认为未正确传递eureka配置的账户密码&#xff0c;例&#xff1a;…...

Qt Graphics View Framework 使用教程

欢迎来到 Qt Graphics View Framework 的世界&#xff01;本教程将引导您了解这一强大工具的基础知识&#xff0c;并教您如何开始使用它来创建丰富的 2D 图形界面。无论您是编程新手还是经验丰富的开发者&#xff0c;本教程都将帮助您快速上手。 基本概念 Qt Graphics View F…...

【调试笔记-20240606-Linux-为 OpenWrt 的 nginx 服务器添加Shell CGI 支持】

调试笔记-系列文章目录 调试笔记-20240606-Linux-为 OpenWrt 的 nginx 服务器添加Shell CGI 支持 文章目录 调试笔记-系列文章目录调试笔记-20240606-Linux-为 OpenWrt 的 nginx 服务器添加Shell CGI 支持 前言一、调试环境操作系统&#xff1a;Windows 10 专业版调试环境调试…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...