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

(算法基础)Floyd算法

适用情景

  1. Floyd算法适用于多源汇最短路,也就是他问你比如说从3号点到6号点的最短路距离,比如说从7号点到20号点的最短路距离,而不是单源最短路(从1号点到n号点的最短路距离)。在这个算法当中允许负权边的存在。但在求最短路距离当中(包括其他算法也一样)是不能够出现负环的,因为这样最短路距离可能变到负无穷去了


时间复杂度

  1. 三重无脑循环,显然O(N^3)。


算法解释

  1. 首先,对于Floyd算法来说,对于图的存储必须要用邻接矩阵来存,不能用邻接表。然后对于邻接矩阵,一开始当然得初始化,这边必须得注意:由于是图,这个矩阵无论是行还是列,有效位都是从一开始。

int dist[N][N];  //N表示图中点的个数+1
  1. 然后Floyd算法是允许这个图当中存在负权边,但是不能出现负环因为在最短路问题当中的话,一旦出现负环,最短路可能变成负无穷)。然后需要对dist数组初始化,这边再提一句:我们现在已经是默认图当中没有负环,好那么现在如果说存在自环的话,肯定是正的,在最短路当中那就不予考虑,于是在初始化的过程当中,如果说i等于j,直接就是0,其他的话就初始化成正无穷,为什么要正无穷?想想就知道了,等会儿我肯定需要min操作

for (int i=1;i<=n;i++)
{for (int j=1;j<=n;j++){if (i==j){dist[i][j]=0;}else{dist[i][j]=0x3f3f3f3f;}}
}
  1. 然后当往这个邻接矩阵当中去输入一条一条图当中的边的时候,由于我们现在是最短路问题,因此我们只需要取小的就可以了,然后如果是自环的话,所以我们默认是没有负环的,因此取小后就是0

while(m--)
{scanf("%d %d %d",&a,&b,&c);dist[a][b]=MIN(dist[a][b],c);
}
  1. 然后接下来就是执行Floyd算法,其实就是三重循环,外循环k从1到n,第二层循环i从1到n,第三层循环j从1到n。然后每一层循环的话就如下比较一下,至于原理的话,这个是与动态规划有关,像我现在的话也掌握不了,先把算法的步骤先记牢吧

for (int k=1;k<=n;k++)
{for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){dist[i][j]=MIN(dist[i][j],dist[i][k]+dist[k][j]);}}
}
  1. 然后当这三重循环结束之后,原先dist数组是用来存边的,现在他已经像孙悟空变身一样,变成了从i到j的最短距离了。当然也有可能的情况就是从i到j的话是走不到的,这时候还谈个屁最短路啊,那如何去判断走不到的这种情况呢?由于是允许存在负权边的情况,因此当在更新的时候有可能会把这个无穷大的值稍微更新了小了一些,因此不能直接dist[ i ][ j ] 等于 0x3f3f3f3f

while(k--)
{scanf("%d %d",&a,&b);if(dist[a][b]>0x3f3f3f3f/2){printf("impossible\n");}else{printf("%d\n",dist[a][b]);}
}

例题

来源:AcWing

854. Floyd求最短路 - AcWing题库

#include <stdio.h>
#define N 210
#define MIN(a,b) ((a)<(b)?(a):(b))
int dist[N][N];
int main()
{int n,m,k,a,b,c;scanf("%d %d %d",&n,&m,&k);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (i==j){dist[i][j]=0;}else{dist[i][j]=0x3f3f3f3f;}}}while(m--){scanf("%d %d %d",&a,&b,&c);dist[a][b]=MIN(dist[a][b],c);}for (int k=1;k<=n;k++){for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){dist[i][j]=MIN(dist[i][j],dist[i][k]+dist[k][j]);}}}while(k--){scanf("%d %d",&a,&b);if(dist[a][b]>0x3f3f3f3f/2){printf("impossible\n");}else{printf("%d\n",dist[a][b]);}}return 0;
}

相关文章:

(算法基础)Floyd算法

适用情景Floyd算法适用于多源汇最短路&#xff0c;也就是他问你比如说从3号点到6号点的最短路距离&#xff0c;比如说从7号点到20号点的最短路距离&#xff0c;而不是单源最短路&#xff08;从1号点到n号点的最短路距离&#xff09;。在这个算法当中允许负权边的存在。但在求最…...

SQL语法:浅析select之七大子句

Mysql版本&#xff1a;8.0.26 可视化客户端&#xff1a;sql yog 目录一、七大子句顺序二、演示2.1 from语句2.2 on子句2.3 where子句2.4 group by子句2.4.1 WITHROLLUP&#xff0c;加在group by后面2.4.2 是否可以按照多个字段分组统计&#xff1f;2.4.3 分组统计时&#xff0c…...

中国人民大学与加拿大女王大学金融硕士——去有光的地方,并成为自己的光

光是我们日常生活中一个重要的元素&#xff0c;试想一下如果没有光&#xff0c;世界将陷入一片昏暗。人生路亦是如此&#xff0c;我们从追逐光、靠近光、直到自己成为光。人民大学与加拿大女王大学金融硕士项目是你人生路上的一束光吗 渴望想要成为一个更好的人&#xff0c;就…...

Python数据结构与算法篇(五)-- 二分查找与二分答案

1 二分法介绍 1.1 定义 二分查找又称折半查找、二分搜索、折半搜索等&#xff0c;是一种在静态查找表中查找特定元素的算法。 所谓静态查找表&#xff0c;即只能对表内的元素做查找和读取操作&#xff0c;不允许插入或删除元素。 使用二分查找算法&#xff0c;必须保证查找表中…...

小游戏也要讲信用

当下&#xff0c;小游戏鱼龙混杂&#xff0c;官方为能更好地保护用户、开发者以及平台的权益&#xff0c;近日宣布7月1日起试行小游戏主体信用分机制。 主体信用分是什么呢&#xff1f;简单来说&#xff0c;这是针对小游戏主体下所有小游戏帐号行为&#xff0c;对开发者进行评…...

贪心算法11

1. 贪心算法的概念 所谓贪心算法是指&#xff0c;在对问题求解时&#xff0c;总是做出在当前看来是最好的选择。也就是说&#xff0c;不从整体最优上加以考虑&#xff0c;他所做出的仅是在某种意义上的局部最优解。 贪心算法没有固定的算法框架&#xff0c;算法设计的关键是贪心…...

【并发编程】JUC并发编程(彻底搞懂JUC)

文章目录一、背景二、什么是JUC&#xff1f;三、JUC框架结构四、JUC框架概述五、JUC中常用类汇总六、相关名词进程和线程进程线程创建线程的几种常见的方式并发和并行用户线程和守护线程七、synchronized 作用范围&#xff1a;八、Lock锁(重点)什么是 Lock锁类型Lock接口lock()…...

Compose 动画 (七) : 高可定制性的动画 Animatable

1. Animatable和animateDpAsState的区别是什么 Animatable是Android Compose动画的底层API&#xff0c;如果我们查看源码&#xff0c;可以发现animateDpAsState内部是调用的animateValueAsState&#xff0c;而animateValueAsState内部调用的是Animatable animateDpAsState比A…...

vue3组件传值

1.父向子传值 父组件 引入子组件 import Son from ./components/Son.vue 设置响应式数据 const num ref(99) 绑定到子组件 <Son :num"num"></Son> 子组件 引入defineProps import { defineProps } from vue; 生成实例接收数据 type设置接收类…...

小白开发微信小程序00--文章目录

一个小白&#xff0c;一个老牛&#xff0c;空手能不能套白羊&#xff0c;能不能白嫖&#xff1f;我告诉你&#xff0c;一切都so easy&#xff0c;这个系列从0到106&#xff0c;屌到上天&#xff0c;盖过任何一个&#xff0c;试问&#xff0c;网上讲微信小程序开发的&#xff0c…...

随手记录第九话 -- Java框架整合篇

框架莫过于Spring了&#xff0c;那就以它为起点吧。 本文只为整理复习用&#xff0c;详细内容自行翻看以前文章。 1.Spring 有人说是Spring成就Java&#xff0c;其实也不是并无道理。 1.1 Spring之IOC控制反转 以XML注入bean的方式为入口&#xff0c;定位、加载、注册&…...

电影《铃芽之旅》观后感

这周看了电影《铃芽之旅》&#xff0c;整部电影是新海诚的新作。电影讲述的是女主铃芽为了关闭往门&#xff0c;在日本旅行中&#xff0c;遭遇灾难的故事。 &#xff08;1&#xff09;往昔记忆-往昔之物 电影中&#xff0c;有很多的“往门”&#xff0c;换成中国的话说&#xf…...

Web自动化测试(二)(全网最给力自动化教程)

欢迎您来阅读和练手&#xff01;您将会从本章的详细讲解中&#xff0c;获取很大的收获&#xff01;开始学习吧&#xff01; 2.4 CSS定位2.5 SeleniumBuilder辅助定位元素2.6 操作元素&#xff08;键盘和鼠标事件&#xff09; 正文 2.4 CSS定位 前言 大部分人在使用selenium定…...

【C语言经典例题!】逆序字符串

目录 一、题目要求 二、解题步骤 ①递归解法 思路 完整代码 ②循环解法 思路 完整代码 嗨大家好&#xff01; 本篇博客中的这道例题&#xff0c;是我自己在一次考试中写错的一道题 这篇博客包含了这道题的几种解法&#xff0c;以及一些我自己对这道题的看法&#xff…...

21 - 二叉树(三)

文章目录1. 二叉树的镜像2. 判断是不是完全二叉树3. 完全二叉树的节点个数4. 判断是不是平衡二叉树1. 二叉树的镜像 #include <ctime> class Solution {public:TreeNode* Mirror(TreeNode* pRoot) {// write code hereif (pRoot nullptr) return pRoot;//这里记得要记得…...

【A-Star算法】【学习笔记】【附GitHub一个示例代码】

文章目录一、算法简介二、应用场景三、示例代码Reference本文暂学习四方向搜索&#xff0c;一、算法简介 一个比较经典的路径规划的算法 相关路径搜索算法&#xff1a; 广度优先遍历&#xff08;BFC&#xff09;深度优先遍历&#xff08;DFC&#xff09;Di jkstra算法&#…...

纽扣电池澳大利亚认证的更新要求

澳大利亚强制性安全和信息标准草案具体规定了对含有纽扣电池和纽扣电池以 及纽扣电池和纽扣电池本身的消费品的要求&#xff0c; 适用范围 1.本法规适用于: 纽扣锂电池(任何尺寸和类型); 直径为16毫米或以上的纽扣锂电池: 一起提供的纽扣电池(未预先安装在产品中)。 2.但是&…...

零代码零距离,明道云开放日北京站圆满结束

文/麦壁瑜 编辑/李雨珂 2023年3月17日&#xff0c;为期一天的明道云开放日北京站圆满结束。本次开放日迎来超过100名伙伴和客户现场参会&#xff0c;其中不乏安利、通用技术集团、民生银行、迈外迪、DELSK集团、中国人民养老保险、北京汽车等知名企业代表。北京大兴机场、作业…...

第五章Vue路由

文章目录相关理解vue-router的理解对SPA应用的理解路由的理解基本路由几个注意点嵌套路由——多级路由路由query参数命名路由路由的params参数路由的props配置路由跳转的replace方法编程式路由导航缓存路由组件路由组件独有的生命钩子activated和deactivated路由守卫全局路由守…...

Git常用指令

Git是什么&#xff1a; Git是分布式版本控制系统&#xff08;Distributed Version Control System&#xff0c;简称 DVCS&#xff09;&#xff0c;分为两种类型的仓库&#xff1a; 本地仓库和远程仓库 第一步先新建仓库&#xff0c;本地 init ,然后提交分枝 链接仓库&#xf…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...