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

【图论】Floyd算法

一.简介

 Floyd算法,也称为Floyd-Warshall算法,是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。

Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两个节点之间的最短路径长度,并通过不断更新这个数组来得到最终的结果。

算法的步骤如下:

  1. 初始化一个二维数组,用于存储节点之间的最短路径长度。
  2. 将数组的初始值设置为图中节点之间的直接距离,如果两个节点之间没有直接连接,则距离为无穷大。
  3. 对于每个节点k,遍历所有节点对(i, j),并尝试通过节点k来优化路径长度。如果通过节点k可以获得更短的路径,则更新数组中的值。
  4. 重复步骤3,直到所有节点对的最短路径长度都被计算出来。

Floyd算法的时间复杂度为O(n^3),其中n是图中节点的数量。它适用于解决稠密图(边数接近节点数的平方)的最短路径问题,但对于稀疏图来说,可能存在更高效的算法。

总的来说,Floyd算法是一种非常经典且实用的算法,可以在有向图或带权图中找到任意两个节点之间的最短路径。


二.存图方法

因为是解决多源最短路,所以使用邻接矩阵存图。


三.原理 

逐渐利用每个点进行搭桥,实现中转功能。过程中带有dp的思想,因为要使用搭完桥之后的最短路径进行再次搭桥,从而实现最优解。


四.核心代码

for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

五.很重要的一道题

P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


六.此题好的原因

考察了对选手floyd算法的进一步理解,而不是单纯的背板子


七.难点

最短路径是很好求的,但题目要求的时间是个大难题。有些路在一个时间点并不能用,更不能起到搭桥作用。所以输出答案时,并不能只考虑起点和终点不能走,还有考虑不能走对其他点最短路的影响。


八.解决方案

既然没到时间就不能用这个点搭桥,那我们在计算整体最短路时不用不就行了吗?在floyd算法中,第一重遍历中的k就是用这个点进行搭桥,那我们就没到时间这前就不遍历即可。


九.参考代码

#include<iostream>
#include<cstdio>
#define N 205
using namespace std;
int n,m;
int a[N];
int f[N][N];//邻接矩阵存边
inline void updata(int k){for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(f[i][j]>f[i][k]+f[j][k])f[i][j]=f[j][i]=f[i][k]+f[j][k];//用这个新的更新所有前面的 return;
}
int main(){cin>>n>>m;for(int i=0;i<n;i++)scanf("%d",a[i]);//依次输入每一个村庄建立完成时需要的时间for(int i=0;i<n;i++)for(int j=0;j<n;j++){f[i][j]=1e9;//初始化为保证它不爆炸范围内的最大值 }for(int i=0;i<n;i++)f[i][i]=0;int s1,s2,s3;for(int i=1;i<=m;i++){scanf("%d%d%d",&s1,&s2,&s3);f[s1][s2]=f[s2][s1]=s3;//初始化边长 }int q;cin>>q;int now=0;for(int i=1;i<=q;i++){//处理各询问 scanf("%d%d%d",&s1,&s2,&s3); //s3为可用时间点 ,s1为x点,s2为y点 while(a[now]<=s3&&now<n){updata(now);//依次更新点,使它可以被用来更新其他的点 now++;}if(a[s1]>s3||a[s2]>s3)cout<<-1<<endl;else {if(f[s1][s2]==1e9)cout<<-1<<endl;else cout<<f[s1][s2]<<endl;}}return 0;
} 

相关文章:

【图论】Floyd算法

一.简介 Floyd算法&#xff0c;也称为Floyd-Warshall算法&#xff0c;是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。 Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两…...

ceph数据分布

ceph的存储是无主结构&#xff0c;数据分布依赖client来计算&#xff0c;有两个条主要路径。 1、数据到PG 2、PG 到OSD 有两个假设&#xff1a; 第一&#xff0c;pg的数量稳定&#xff0c;可以认为保持不变&#xff1b; 第二&#xff0c; OSD的数量可以增减&#xff0c;OSD的…...

mysql的两张表left join 进行关联后,索引进行优化案例

一 mysql的案例 1.1 不加索引情况 1.表1没加索引 2.表2没加索引 3.查看索引 1.2 添加索引 1.表1添加索引 2.表2添加索引 3.查看...

2018年3月全国计算机等级考试真题(语言二级C)

2018年3月全国计算机等级考试真题&#xff08;语言二级C&#xff09; 第1题 设有定义&#xff1a;char s[81]&#xff1b;int i0&#xff1b;以下不能将一行带有空格的字符串正确读入的语句或语句组是 A. while((s[i]getchar())!\n);s[i]\0; B. scanf("%s",s); C.…...

java.util.Timer简介以及简单使用示例

一、简介 定时器&#xff08;Timer&#xff09;是一个工具类&#xff0c;用于安排任务&#xff08;java.util.TimerTask&#xff09;在指定时间后执行或以指定的时间间隔重复执行。它可以用于执行定时任务、定时调度和时间延迟等操作。 定时器&#xff08;Timer&#xff09;可以…...

C语言笔试训练【第12天】

文章目录 1、请阅读以下程序&#xff0c;其运行结果是&#xff08; &#xff09;2、假设编译器规定 int 和 short 类型长度分别为32位和16位&#xff0c;若有下列C语言语句&#xff0c;则 y 的机器数为&#xff08; &#xff09;3、下列程序的输出结果是什么&#xff08; &…...

外网连接局域网的几种方式?快解析内网穿透安全便利吗?

外网连接局域网是一项网络连接中的关键技术&#xff0c;它能够让远程用户通过互联网访问内部局域网中的资源和服务。外网连接局域网为企业提供了更大的灵活性和便捷性&#xff0c;但也需要严格的安全措施来防止未经授权的访问。 外网连接局域网的几种方式 在将外网连接到局域…...

基于互斥锁的生产者消费者模型

文章目录 生产者消费者 定义代码实现 / 思路完整代码执行逻辑 / 思路 局部具体分析model.ccfunc&#xff08;消费者线程&#xff09; 执行结果 生产者消费者 定义 生产者消费者模型 是一种常用的 并发编程模型 &#xff0c;用于解决多线程或多进程环境下的协作问题。该模型包含…...

USB隔离器电路分析,SA8338矽塔sytatek电机驱动,源特科技VPS8701,开关电源,电源 大师

一、 USB隔离器电路分析 进行usb隔离可以使用USB隔离模块 ADUM3160 ADUM4160 注意&#xff1a;B0505S 最大带载0.16A&#xff0c;副边需要带载能力需要改变方案 比如移动硬盘至少需要0.5A 用充电宝、18650、设计5V1A输出电源 二、 1A隔离电压方案...

TPC-DS 测试是否支持 Glue Data Catalog?

在上一篇文章《在Hive/Spark上执行TPC-DS基准测试 (PARQUET格式)》中,我们详细介绍了具体的操作方法,当时的集群使用的是Hive Metastore,所有操作均可成功执行。当集群启用 Glue Data Catalog 时,在执行add_constraints.sql时会报错: Optimizing table date_dim (1/24).…...

网络编程(8.14)TCP并发服务器模型

作业&#xff1a; 1. 多线程中的newfd&#xff0c;能否修改成全局&#xff0c;不行&#xff0c;为什么&#xff1f; 2. 多线程中分支线程的newfd能否不另存&#xff0c;直接用指针间接访问主线程中的newfd,不行&#xff0c;为什么&#xff1f; 多线程并发服务器模型原代码&…...

认识负载均衡||WEBSHELL

目录 一、负载均衡 1.nginx负载均衡算法 2.nginx反向代理-负载均衡 二、webshell 1.构造不含数字和字母的webshell 2.如何绕过 一、负载均衡 1.nginx负载均衡算法 &#xff08;1&#xff09;轮询&#xff08;默认&#xff09;每个请求按时间顺序逐一分配到不同的后端服务&…...

Chapter 15: Object-Oriented Programming | Python for Everybody 讲义笔记_En

文章目录 Python for Everybody课程简介Object-oriented programmingManaging larger programsGetting startedUsing objectsStarting with programsSubdividing a problemOur first Python objectClasses as typesObject lifecycleMultiple instancesInheritanceSummaryGlossa…...

模板编程-成员特化

成员特化:类模板特化除了可以对整个类进行特化外,可以只针对某部分成员函数进行特化 全类特化和成员特化都属于全局特化 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstring>template<typename T> class CMath { public:CMath(const…...

信安通用基础知识

文章目录 密码学经典误区PGP优良保密协议信安经典其它安全手段XSS与CSRF cross site request forgeryCSRF的利用逻辑CSRF示例CSRF防范检查Referer字段添加校验token XSS cross site scripting common weakness enumeration常见密码api误用&#xff08;摘自毕设参考文献&#xf…...

网上购物系统的设计与实现/在线商城/基于spring boot的电商平台/基于Java的商品销售系统

摘 要 本毕业设计的内容是设计并且实现一个基于Springboot的网上购物系统。它是在Windows下&#xff0c;以MYSQL为数据库开发平台&#xff0c;Tomcat网络信息服务作为应用服务器。网上购物系统的功能已基本实现&#xff0c;主要包括用户管理、数码分类管理、数码产品管理、服…...

uniapp项目-配置store文件夹

1.创建store.js 说明&#xff1a;创建一个新的 Vuex Store 实例&#xff0c;配置 Store 中的模块。 import Vue from vue; import Vuex from vuex; // 导入两个 Vuex 模块&#xff1a;moduleCart 和 moduleUser import moduleCart from /store/cart.js; import moduleUser fr…...

element表格多选实现

表格实现多选 实现表格多选很简单&#xff0c;只需要在表格里加上一列即可&#xff0c;加完之后就会在表格里出现一列白色的四方块按钮&#xff0c;可以多选&#xff0c;也可以单选 <el-table-columntype"selection"width"55"align"center"&…...

宠物智能自动喂食器方案设计

据相关数据表明&#xff0c;2019年全国城镇宠物犬猫数量达到9915万只&#xff0c;增幅达到8.4%&#xff0c;消费市场规模达2024亿元&#xff0c;比2018年增长18.5%&#xff0c;整体呈现持续大幅增长的态势。而养宠人群的主力&#xff0c;为25岁至38岁年轻人&#xff0c;都市白领…...

学习笔记230818---对于promise失败状态处理的重要性

问题描述&#xff1a; 在项目中经常会出现如上的问题&#xff0c;这是因为&#xff0c;用promise封装的接口或第三方组件方法&#xff0c;如果只对成功的状态做处理&#xff0c;就会造成页面出错&#xff0c;报error。 解决方法 then()的末尾加上.catch(()>{})对失败的状态…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...

CppCon 2015 学习:REFLECTION TECHNIQUES IN C++

关于 Reflection&#xff08;反射&#xff09; 这个概念&#xff0c;总结一下&#xff1a; Reflection&#xff08;反射&#xff09;是什么&#xff1f; 反射是对类型的自我检查能力&#xff08;Introspection&#xff09; 可以查看类的成员变量、成员函数等信息。反射允许枚…...

Linux操作系统共享Windows操作系统的文件

目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项&#xff0c;设置文件夹共享为总是启用&#xff0c;点击添加&#xff0c;可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download&#xff08;这是我共享的文件夹&#xff09;&…...

OPENCV图形计算面积、弧长API讲解(1)

一.OPENCV图形面积、弧长计算的API介绍 之前我们已经把图形轮廓的检测、画框等功能讲解了一遍。那今天我们主要结合轮廓检测的API去计算图形的面积&#xff0c;这些面积可以是矩形、圆形等等。图形面积计算和弧长计算常用于车辆识别、桥梁识别等重要功能&#xff0c;常用的API…...