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

Vim 调用外部命令学习笔记

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

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...