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

图论进阶之路-最短路(Floyd)

时间复杂度:O(n^3)

使用场景:当需要得知任意两个点的最短距离以及其路径时使用

准备:需要两个矩阵

一个记录最短距离(D)

一个记录最短路径的最后一个结点(P)

其核心在于不断的判断越过中间结点是否比不越过中间节点距离更短,迭代的结果也会影响到后面的路径的更新,通过不断的更新,使得每两个节点直接的距离被都更新到最短

具体过程:

 d4573be44ccf4e819af51be9bff213b1.png

1.初始化 D,P 矩阵,D 矩阵初始化为所有结点的入度距离,P 矩阵 初始化为所有结点的入度结点

        int MAX = Integer.MAX_VALUE;int[][] D = {{MAX,MAX,MAX,MAX,  6},{  9,MAX,  3,MAX,MAX},{  2,MAX,MAX,  5,MAX},{MAX,MAX,MAX,MAX,  1},{MAX,MAX,MAX,MAX,MAX}};int[][] P = {{-1,-1,-1,-1, 0},{ 1,-1, 1,-1,-1},{ 2,-1,-1, 2,-1},{-1,-1,-1,-1, 3},{-1,-1,-1,-1,-1}};

2.将每一个点都做一次中间结点

3.在当前中间节点的基础上,遍历所有结点,更新最短路

关于两个矩阵更新规则:

  • D: 根据上一次的 D ,若 遍历到的结点到中间结点 + 中间结点到目标结点 < 上一次遍历到的结点到目标结点,就更新
  • P: 若 D 发生变动,则将路径更新为 上一次 中间结点到目标节点的路径

共五个结点,故我们需要重复 5 次 2,3 步骤

public static void main(String[] args) {int MAX = Integer.MAX_VALUE/2;int[][] D = {{MAX,MAX,MAX,MAX,  6},{  9,MAX,  3,MAX,MAX},{  2,MAX,MAX,  5,MAX},{MAX,MAX,MAX,MAX,  1},{MAX,MAX,MAX,MAX,MAX}};int[][] P = {{-1,-1,-1,-1, 0},{ 1,-1, 1,-1,-1},{ 2,-1,-1, 2,-1},{-1,-1,-1,-1, 3},{-1,-1,-1,-1,-1}};for(int k=0;k<5;k++) {//中间结点	//遍历所有的结点对for(int i=0;i<5;i++) {for(int j=0;j<5;j++) {if(D[i][k] + D[k][j] < D[i][j]) {D[i][j] = D[i][k] + D[k][j];P[i][j] = P[k][j];}}}}}

当中间点为 0 时,两个矩阵的更新结果为:

 

[∞, ∞, ∞, ∞, 6]

[9, ∞, 3, ∞, 15]

[2, ∞, ∞, 5, 8]

[∞, ∞, ∞, ∞, 1]

[∞, ∞, ∞, ∞, ∞]

---------------------------------

[-1, -1, -1, -1, 0]

[1, -1, 1, -1, 0]

[2, -1, -1, 2, 0]

[-1, -1, -1, -1, 3]

[-1, -1, -1, -1, -1]

=================================

 

当中间点为 1 时,两个矩阵的更新结果为:

 

[∞, ∞, ∞, ∞, 6]

[9, ∞, 3, ∞, 15]

[2, ∞, ∞, 5, 8]

[∞, ∞, ∞, ∞, 1]

[∞, ∞, ∞, ∞, ∞]

---------------------------------

[-1, -1, -1, -1, 0]

[1, -1, 1, -1, 0]

[2, -1, -1, 2, 0]

[-1, -1, -1, -1, 3]

[-1, -1, -1, -1, -1]

=================================

 

当中间点为 2 时,两个矩阵的更新结果为:

 

[∞, ∞, ∞, ∞, 6]

[5, ∞, 3, 8, 11]

[2, ∞, ∞, 5, 8]

[∞, ∞, ∞, ∞, 1]

[∞, ∞, ∞, ∞, ∞]

---------------------------------

[-1, -1, -1, -1, 0]

[2, -1, 1, 2, 0]

[2, -1, -1, 2, 0]

[-1, -1, -1, -1, 3]

[-1, -1, -1, -1, -1]

=================================

 

当中间点为 3 时,两个矩阵的更新结果为:

 

[∞, ∞, ∞, ∞, 6]

[5, ∞, 3, 8, 9]

[2, ∞, ∞, 5, 6]

[∞, ∞, ∞, ∞, 1]

[∞, ∞, ∞, ∞, ∞]

---------------------------------

[-1, -1, -1, -1, 0]

[2, -1, 1, 2, 3]

[2, -1, -1, 2, 3]

[-1, -1, -1, -1, 3]

[-1, -1, -1, -1, -1]

=================================

 

当中间点为 4 时,两个矩阵的更新结果为:

 

[∞, ∞, ∞, ∞, 6]

[5, ∞, 3, 8, 9]

[2, ∞, ∞, 5, 6]

[∞, ∞, ∞, ∞, 1]

[∞, ∞, ∞, ∞, ∞]

---------------------------------

[-1, -1, -1, -1, 0]

[2, -1, 1, 2, 3]

[2, -1, -1, 2, 3]

[-1, -1, -1, -1, 3]

[-1, -1, -1, -1, -1]

=================================

4.若最后需要得到最短路路径:可以通过 先找到 路径矩阵的位置,得到前一个点,再找到该点与前一个点的前一个点,直到前一个点变成自身为止

如:我们要找到 v1 到 v0 的最短路径

先找到 1 -> 0 的最近的前一个结点,也就是 P[1][0]  = 2

得知了前一个结点为 2 ,记录路径 2 -> 0

继续往前找,1 -> 2 的前一个结点,也就是 P[1][2] = 1

得知了前一个结点为 1,记录路径 1 -> 2 -> 0

再继续往前就是寻找 1 -> 1 ,自己找自己的时候就代表路径已经完整了

故 v1 到 v0 的最短路径为: 1 -> 2 -> 0

 

 

相关文章:

图论进阶之路-最短路(Floyd)

时间复杂度&#xff1a;O(n^3) 使用场景&#xff1a;当需要得知任意两个点的最短距离以及其路径时使用 准备&#xff1a;需要两个矩阵 一个记录最短距离&#xff08;D&#xff09; 一个记录最短路径的最后一个结点&#xff08;P&#xff09; 其核心在于不断的判断越过中间…...

安装sqllab靶机之后,练习关卡报403 forbidden

解决办法&#xff1a; 在nginx的conf文件中添加上访问index.php vim /usr/local/nginx/conf/nginx.conf 保存退出 再重启一下nginx&#xff0c;就完成了。 ./nginx -s reload...

微信VX多开 免扫码 登录 互斥体 可视化 Exui v1.1 易语言源码附成品软件

UI设计&#xff1a; 1. EXUI界面库20240204 调用的模块&#xff1a; 1. wow64_hook_3.02.ec&#xff08;压缩包内含&#xff09; 2. 精易模块[v11.1.0].ec&#xff08;自行下载&#xff09; 更新日志&#xff1a; v1.1 2024年7月25日13:28:43 { 1. 有人反馈 设置了V…...

JavaEE 从入门到精通(一) ~ Maven

晚上好&#xff0c;愿这深深的夜色给你带来安宁&#xff0c;让温馨的夜晚抚平你一天的疲惫&#xff0c;美好的梦想在这个寂静的夜晚悄悄成长。 目录 前言 1.1 概念 什么是 Maven&#xff1f; Maven 的核心概念 1.2 maven依赖坐标 1.3 maven仓库 1.4 maven安装 1.5 mave…...

滚珠丝杆与丝杆支撑座:稳定性与精度的双重保障

丝杆支撑座是连接滚珠丝杆与电机的轴承&#xff0c;采用优质的轴承能确保支撑座与滚珠丝杆之间的刚性平衡。那么&#xff0c;滚珠丝杆搭连接杆支撑座有哪些优缺点呢&#xff1f; 正常情况下&#xff0c;丝杆支撑座能够提供稳定的支撑力&#xff0c;确保滚珠丝杆在复杂工况下保持…...

实验5-11 空心的数字金字塔

本题要求实现一个函数&#xff0c;输出n行空心的数字金字塔。 函数接口定义&#xff1a; void hollowPyramid( int n );其中n是用户传入的参数&#xff0c;为[1, 9]的正整数。要求函数按照如样例所示的格式打印出n行空心的数字金字塔&#xff0c;请注意&#xff0c;最后一行的…...

C#对象和类型

属性、方法、字段 字段和属性的区别 在C#中&#xff0c;字段&#xff08;fields&#xff09;和属性&#xff08;properties&#xff09;都是类的成员&#xff0c;它们提供了类存储数据的方式&#xff0c;但它们在用途和功能上有着明显的区别。 字段 字段通常用来存储类…...

免费分享一套SpringBoot+Vue图书(图书借阅)管理系统【论文+源码+SQL脚本】,帅呆了~~

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的SpringBootVue图书(图书借阅)管理系统&#xff0c;分享下哈。 项目视频演示 【免费】SpringBootVue图书(图书借阅)管理系统 Java毕业设计_哔哩哔哩_bilibili 项目介绍 本论文阐述了一套先进的图书管理系…...

数据结构与算法--队列

文章目录 提要队列的定义队列的认识队列的应用队列的抽象数据类型队列的存储结构队列的链式存储结构与实现链队的进队和出队操作链队的数据类型初始化链队列入队操作出队操作队列的顺序存储结构与实现顺序队列的假溢出问题队列上溢循环队列循环队列取下一相邻单元下标运算队满与…...

<Qt> 常用控件

目录 一、控件概述 二、QWidget 核心属性 &#xff08;一&#xff09;QWidget的核心属性概览 1. enabled 2. geometry 3. WindowFrame的影响 4. windowTitle 5. window Icon 6. windowOpacity 7. cursor 8. font 9. toolTip 10. focusPolicy 11. styleSheet 三、…...

关于C/C++的编译、构建、CMake、x86_amd64等问题(自用)

被这些玩意整红温了 编译器版本 x86&#xff1a;编译器为x86版本&#xff0c;输出文件为x86。amd64_x86&#xff1a;编译器为amd64版本&#xff0c;输出文件为x86。amd64&#xff1a;编译器为amd64版本&#xff0c;输出文件为amd64。x86_amd64&#xff1a;编译器为x86版本&am…...

【设计模式】工厂模式详解

1.简介 工厂模式是一种创建型设计模式&#xff0c;通过提供一个接口或抽象类来创建对象&#xff0c;而不是直接实例化对象。工厂模式的主要思想是将对象的创建与使用分离&#xff0c;使得创建对象的过程更加灵活和可扩展。 工厂模式主要包括以下角色&#xff1a; 抽象工厂&a…...

【Spring Boot】用 Spring Security 实现后台登录及权限认证功能

用 Spring Security 实现后台登录及权限认证功能 1.引入依赖2.创建权限开放的页面3.创建需要权限验证的页面4.配置 Spring Security4.1 配置 Spring MVC4.2 配置 Spring Security 5.创建登录页面6.测试权限 1.引入依赖 使用前需要引入相关依赖&#xff0c;见以下代码&#xff…...

PHP开发【石头剪刀布小游戏】

石头剪刀布小游戏 玩法超级简单&#xff0c;你只需要在下面选择石头、剪刀或者布&#xff0c;然后提交&#xff0c;系统就会随机生成电脑的选择&#xff0c;告诉你最终的结果哦&#xff01; 游戏规则&#xff1a; 如果你的选择和电脑一样&#xff0c;那么就是平局。如果你赢…...

(leetcode学习)42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表…...

Python编程实例2

一、通过用户输入数字计算阶乘 # 获取用户输入的数字 num int(input("请输入一个数字: ")) factorial 1 # 查看数字是负数&#xff0c;0 或 正数 if num < 0:print("抱歉&#xff0c;负数没有阶乘") elif num 0:print("0 的阶乘为 1") e…...

排序算法:堆排序,golang实现

目录 前言 堆排序 代码示例 1. 算法包 2. 堆排序代码 3. 模拟程序 4. 运行程序 5. 从大到小排序 堆排序的思想 堆排序的实现逻辑 1. 构建最大堆 2. 排序 循环次数测试 假如 10 条数据进行排序 假如 20 条数据进行排序 假如 30 条数据进行排序 假设 5000 条数据…...

【网络安全入门】学习网络安全必须知道的77个网络基础知识

1、TCP/IP 协议的四层模型&#xff08;网络接口层、网络层、传输层、应用层&#xff09; TCP/IP 协议是互联网通信的基础&#xff0c;四层模型中&#xff0c;网络接口层负责与物理网络的连接&#xff1b;网络层主要处理 IP 数据包的路由和转发&#xff1b;传输层提供端到端的可…...

limit 以及分页 SQL 语句

目录 1. 作用 2. 演示 3. 分页 SQL 语句 1. 作用 获取结果集的一部分&#xff1b; 2. 演示 &#xff08;1&#xff09;如下&#xff0c;获取表的前三行&#xff1b; &#xff08;2&#xff09;只有一个数字&#xff0c;默认从 0 开始&#xff1b; &#xff08;3&#x…...

mysql8.0规范

MySQL 数据库开发规范 目录 背景与目标规范列表 1. 库表设计 1.1 必须字段1.2 命名规范 2. 定义规范 2.1 约束规范2.2 类型规范 2.2.1 字段类型与长度2.2.2 状态字段数据类型2.2.3 布尔型2.2.4 varchar和text, json2.2.5 decimal(m,d) 3. 索引规范4. 其他规范5. SQL 使用 5.…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...