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

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...