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

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

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

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

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...