【算法】Floyd多源最短路径算法

目录

一、概念

二、思路

三、代码


一、概念

在前面的学习中,我们已经接触了Dijkstra、Bellman-Ford等单源最短路径算法。但首先我们要知道何为单源最短路径,何为多源最短路径

  • 单源最短路径:从图中选取一点,求这个点到图中其他节点的最短路径
  • 多源最短路径:从图中任选两个节点,我们都能知道这两点间的最短路径

Floyd多源最短路径算法可用于求图中任意两点间的最短路径长,其核心思路在于依次将每个节点作为路径的中间点来更新其他任意两点的较优解,最后得到全局最优解


二、思路

1.首先我们需要一个图,和二维数组g、path

其中:

  • g用于存储从i到j的最短路径长度
  • path用于存储从i到j的最短路径的终点 的 前继节点

例如初始时,从1到2的最短路径就是权重为6的边,其终点为2,而对于这条路径而言2的前继节点为1,因此path[1][2] = 1

g(0)和path(0)意为矩阵g和path的初始态。因为初始时两个节点之间的最短路径就是他们之间的边,因此我们在初始化这两个数组时,只需要按照样例输入的边填写矩阵g即可

若从i到j之间没有边,则填最大值即可,例如g[3][2] = MAX,因为没有从3指向2的边

而矩阵path在初始化时按照上面的规则初始化即可,例如初始从3到1的最短路径就是3->1,终点为1,前继节点为3,因此path[3][1] = 3

2. 从1号节点开始,将每个节点作为任意两个节点的最短路径的中间点

有的人听到这里可能已经懵了,我们跟着图慢慢走

此时g(0)、path(0)变为g(1)和path(1),代表接下来要更新 i->1->j 的最短路径

但是我们并不需要将矩阵g和矩阵path中的所有值都更新,例如g[1][2],判断1->1->2的路径是否比1->2的最短路径更短是不具有价值的。两个矩阵中,如果行标和中间节点一样、列标和中间节点一样或者行标和列标一样的话,我们直接跳过即可

因此,只有2->1->3的情况,和3->1->2的情况需要讨论

(带虚线的位置代表不需要判断)

可以看到,2->1->3的距离为2->1的最短距离加1->3的最短距离,即g[2][1]+g[1][3] = 23,这个距离并不比g[2][3]小,因此不需要更新

而3->1->2的距离为11,小于原来的值MAX,因此更新,同时path[3][2]也更新为3->1->2的终点的前继节点即1

3.重复第二步直到所有节点都已作为中间点

1->2->3的距离为g[1][2]+g[2][3] = 10,比原来的13更小,因此将g[1][3]更新,path[1][3] = 2

3->2->1的距离为g[3][2]+g[2][1] = 21,比g[3][1]大,不更新

1->3->2的距离为21,比g[1][2]大,不更新

2->3->1的距离为g[2][3]+g[3][1] = 9,比原来的10更小,因此将g[2][1]更新,path[2][1] = 3

至此,我们就得到了图中任意两点间的最短路径长度了

而最短路径本身,则可以根据矩阵path中的值推出来,例如要求从2到1的最短路径,首先知道终点为节点1,根据path[2][1]知道下一个节点3,再根据path[2][3]知道下一个节点2,最后path[2][2]为-1说明路径走到结尾,因此完整的最短路径就为2->3->1


三、代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f
using namespace std;#define N 210
#define M 20010int n, m, k;
int g[N][N]; //存储从i到j的最短路径长度
int path[N][N] = {-1}; //path[i][j]存储从i到j最短路径的终点 的 前继节点void Floyd()
{for(int i = 1; i <= n; i++){g[i][i] = 0; //自己到自己的路径长度设置为0path[i][i] = -1; //自己到自己的路径设置为-1}for(int k = 1; k <= n; k++) //代表从i经过k到j的最短路径{for (int i = 1; i <= n; i++) //第i行{for (int j = 1; j <= n; j++) //第j列{if(i == j || i == k || j == k) //多余情况continue;if(g[i][k] + g[k][j] < g[i][j]) //从i经过k到j的最短路径 比 原先从i到j的最短路径更短{g[i][j] = g[i][k] + g[k][j]; //更新从i到j的最短路径path[i][j] = path[k][j]; //更新从i到j最短路径的终点 的 前继节点}}}}
}void solve()
{memset(g, 0x3f, sizeof g);cin >> n >> m >> k;for(int i = 0;i < m; i++){int a, b, w;cin >> a >> b >> w;g[a][b] = min(g[a][b], w); //可能存在重边path[a][b] = a; //初始时从a到b最短路径终点的前继节点就是a本身}Floyd(); //Floyd算法for (int i = 0; i < k; i++){int a, b;cin >> a >> b;if(g[a][b] > INF / 2)cout << "impossible" << endl;elsecout << g[a][b] << endl;}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while(t--)solve();return 0;
}

完.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/465019.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Docker安装MongoDB详解(mongo.latest)

一、MongoDB介绍 MongoDB是一种基于分布式文件存储的数据库&#xff0c;使用C语言开发&#xff0c;旨在为Web应用提供可扩展且高性能的数据存储解决方案。作为一种介于关系数据库和非关系数据库之间的技术&#xff0c;MongoDB具有强大的功能和高效的性能&#xff0c;特别适用于…

金箍棒变化-第15届蓝桥杯国赛Scratch初/中级组真题第1题

[导读]&#xff1a;超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成&#xff0c;后续会不定期解读蓝桥杯真题&#xff0c;这是Scratch蓝桥杯真题解析第193讲。 如果想持续关注Scratch蓝桥真题解读&#xff0c;可以点击《Scratch蓝桥杯历年真题》并订阅合集&#xff0c;…

简单的 docker 部署ELK

简单的 docker 部署ELK 这是我的运维同事部署ELK的文档&#xff0c;我这里记录转载一下 服务规划 架构: Filebeat->kafka->logstash->ES kafka集群部署参照: kafka集群部署 部署服务程序路径/数据目录端口配置文件elasticsearch/data/elasticsearch9200/data/elas…

Unity XR Interaction Toolkit 开发教程(3)快速配置交互:移动、抓取、UI交互【3.0以上版本】

获取完整课程以及答疑&#xff0c;工程文件下载&#xff1a; https://www.spatialxr.tech/ 视频试看链接&#xff1a; 3.快速配置交互&#xff1a;移动、抓取、UI交互【Unity XR Interaction Toolkit 跨平台开发教程】&#xff08;3.0以上版本&#xff09; 系列教程专栏&…

深度体验SCNet超算平台:SCNet「AI跃升季」·谁是下一个“AI”跃人?

平时做大模型训练的时候总是苦于没有服务器资源来做微调实验&#xff0c;于是这次深度体验了一下SCNet超算平台。 SCNet超算平台是一个超算互联网计算服务平台&#xff0c;有着更大更全更专业的超级算力。显卡从异构加速卡到A800都有。 本次我尝试了大模型的推理和微调。 第一…

求助帖【如何学习核磁共振的原理】

最近提前进组了 我完全不懂磁共振的相关知识 想问问各位大佬有没有推荐的学习路线 或者是学习资料、论坛都可以的&#xff08;我做的方向是磁共振成像技术&#xff09; 老师给了一本书&#xff0c;但是有点看不懂&#xff0c;全英文的 叫Principles Of Magnetic Resonance …

MySQL查询where中包含多个in条件问题

示例&#xff1a; select * from x_table where a in (1,2,3) and b in (4,8) 上面这种查询方法&#xff0c;如果可以通过a和b唯一确定一条数据&#xff0c;但a和b列可以有相同值时&#xff0c;会造成查询数据不准确。 验证&#xff1a; 假设有以下数据&#xff08;手机号为…

HiveSQL 中判断字段是否包含某个值的方法

HiveSQL 中判断字段是否包含某个值的方法 在 HiveSQL 中&#xff0c;有时我们需要判断一个字段是否包含某个特定的值。下面将介绍几种常用的方法来实现这个功能。 一、创建示例表并插入数据 首先&#xff0c;我们创建一个名为employee的表&#xff0c;并插入一些示例数据&am…

python-读写Excel:openpyxl-(4)下拉选项设置

使用openpyxl库的DataValidation对象方法可添加下拉选择列表。 DataValidation参数说明&#xff1a; type&#xff1a; 数据类型("whole", "decimal", "list", "date", "time", "textLength", "custom"…

求平面连接线段组成的所有最小闭合区间

这个功能确实非常实用&#xff0c;我在过去开发地面分区编辑器时就曾应用过这一算法。最近&#xff0c;在新产品的开发中再次遇到了类似的需求。尽管之前已经实现过&#xff0c;但由于长时间未接触&#xff0c;对算法的具体细节有所遗忘&#xff0c;导致重新编写时耗费了不少时…

springboot - 定时任务

定时任务是企业级应用中的常见操作 定时任务是企业级开发中必不可少的组成部分&#xff0c;诸如长周期业务数据的计算&#xff0c;例如年度报表&#xff0c;诸如系统脏数据的处理&#xff0c;再比如系统性能监控报告&#xff0c;还有抢购类活动的商品上架&#xff0c;这些都离不…

ES管理工具Cerebro 0.8.5 Windows版本安装及启动

前言&#xff1a; Cerebro 的下载地址 https://github.com/lmenezes/cerebro/releases Cerebro 默认监听IP 0.0.0.0 &#xff0c;默认端口9000&#xff0c;访问地址&#xff1a;http://localhost:9000 启动 cmd命令到安装目录下&#xff1a;cerebro-0.8.5\bin 执行命令 ce…

Flutter 正在切换成 Monorepo 和支持 workspaces

其实关于 Monorepo 和 workspaces 相关内容在之前《Dart 3.5 发布&#xff0c;全新 Dart Roadmap Update》 和 《Flutter 之 ftcon24usa 大会&#xff0c;创始人分享 Flutter 十年发展史》 就有简单提到过&#xff0c;而目前来说刚好看到 flaux 这个新进展&#xff0c;所以就再…

[论文][环境]3DGS+Colmap环境搭建_WSL2_Ubuntu22.04 - 副本

0. 前言 仅使用Ubuntu进行场景编译&#xff0c;场景渲染查看则使用Windows下官方提供的编译好的预编译包打开即可&#xff0c;非常方便&#xff08;要注意即使是预编译版本&#xff0c;Windows端也应该安装VS和CUDA Toolkit&#xff0c;要注意的是&#xff0c;最新的SIBR预编译…

json-server的使用(根据json数据一键生成接口)

一.使用目的 在前端开发初期&#xff0c;后端 API 可能还未完成&#xff0c;json-server 可以快速创建模拟的 RESTful API&#xff0c;帮助前端开发者进行开发和测试。 二.安装 npm install json-server //局部安装npm i json-server -g //全局安装 三.使用教程 1.准备一…

导入和部署自定义 LLM 大模型

本文以【Qwen2-7B-Instruct】模型为例&#xff0c;指导如何将自定义大模型导入到 TI 平台&#xff0c;并使用平台内置推理镜像部署大模型对话推理服务。 前置要求 申请 CFS 本文所涉及到的操作需要通过 CFS 存储模型文件&#xff0c;详情请查看创建文件系统及挂载点。 操作…

开源办公软件 ONLYOFFICE 深入探索

文章目录 引言1. ONLYOFFICE 创建的背景1. 1 ONLYOFFICE 项目启动1. 2 ONLYOFFICE 的发展历程 2. 核心功能介绍2. 1 桌面编辑器2. 1. 1 文档2. 1. 2 表格2. 1. 3 幻灯片 2. 2 协作空间2. 3 文档编辑器 - 本地部署版 3. 技术介绍4. 安装5. 优势与挑战6. 个人体验7. 强大但不止于…

HTTP慢速攻击原理及解决办法

目录 引言 HTTP慢速攻击原理 解决办法 Nginx Tomcat 华宇TAS IIS 结论 引言 HTTP慢速攻击&#xff08;Slow HTTP Attack&#xff09;是一种拒绝服务攻击&#xff08;DoS&#xff09;&#xff0c;攻击者通过故意缓慢地发送HTTP请求来耗尽服务器资源&#xff0c;导致合法…

[mysql]修改表和课后练习

目录 DDL数据定义语言 添加一个字段 添加一个字段到最后一个 添加到表中的第一个一个字段 选择其中一个位置: 修改一个字段:数据类型,长度,默认值(略) 重命名一个字段 删除一个字段 重命名表 删除表 清空表 DCL中事务相关内容 DCL中COMMIT和ROLLBACK的讲解 对比TR…

SpringBoot+ClickHouse集成

前面已经完成ClickHouse的搭建&#xff0c;创建账号&#xff0c;创建数据库&#xff0c;保存数据库等&#xff0c;接下来就是在SpringBoot项目中集成ClickHouse。 一&#xff0c;引入依赖 <!-- SpringBoot集成ClickHouse --> <dependency><groupId>com.baom…