当前位置: 首页 > 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 专业版调试环境调试…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...