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

图论-最短路算法

1. Floyd算法

  • 作用:用于求解多源最短路,可以求解出任意两点的最短路

  • 利用动态规划只需三重循环即可(动态规划可以把问题求解分为多个阶段)
  • 定义dp[k][i][j]表示点i到点j的路径(除去起点终点)中最大编号不超过k的情况下,点i到点j的最短距离。
  • 当加入第k个点作为i到j的中间点:dp[k]][i][j] = min(dp[k - 1]][i][j]], dp[k - 1][i][k] + dp[k - 1][k][j])

发现可以使用滚动数组优化第一维度:

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

枚举所有k,判断是否可以作为中间点,可以作为中间点则优化最短路。

初始化:如果<i, j>无边,则dp[i][j] = INF, 有边则等于边权;dp[i][i] = 0(自己到自己是不用走的)

为了理解更深刻,简单举个例子:

各点之间的关系用邻接矩阵保存(下图中又两个邻接矩阵,一个是两点之间的最短距离,还有一个是两点之间的最短路中经过的节点。)

更新

每次基于之前能找到的最短路径,如果比它短就更新。

以2号节点作为中转站是基于1号节点作为中转站的,经过n轮递推就可以得到最终答案(任意两点的最短路)

例题:

蓝桥1121

为什么先遍历k,之后遍历i,j?

因为要符合顺序,遍历完中间点后, 就要遍历邻接矩阵,进行最短距离的更新。

import os
import sys# 请在此输入您的代码
n, m, q = map(int, input().split())
INF = 10 ** 18
# dp[i][j]表示i到j的最短路
dp = [[INF] * (n + 1) for i in range(n + 1)] # 初始值设较大值
for i in range(1, n + 1):dp[i][i] = 0 # 自己到自己的距离为0
for _ in range(m):u, v, w = map(int, input().split())dp[u][v] = dp[v][u] = min(dp[u][v], w) # 双向边/无向边(可能有重边)# Floyd算法模板
# dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
for k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])for _ in range(q):u, v = map(int, input().split())if dp[u][v] == INF:print(-1)else:print(dp[u][v])

蓝桥8336

import os
import sys# 请在此输入您的代码
"""
翻译题意:有n个城市,m条边就是有m条路径可以流通,每个城市有自己的商品产出,可以拿去别的地方销售,
需要求出最大利润,但是商品产量ai是不变的,生产成本pi也是不变的,只有售卖单价会随着商品运输到其他
城市会改变,以及带来的运输费用(这里的运输费用有一个路径的问题,需要用最短路算出来最少支付。
"""n, m = map(int, input().split())
# g = s - p - f(路径费用)
INF = 10 ** 17
a, p, s = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1) # 商品的产量, 生产成本, 售卖单价
f = [[INF] * (n + 1) for i in range(n + 1)] # 记录最短路(也就是最短的运输费用)
g = [[0] * (n + 1) for i in range(n + 1)] # 记录利润
for i in range(1, n + 1):a[i], p[i], s[i] = map(int, input().split())
for _ in range(1, m + 1):u, v, w = map(int, input().split())f[u][v] = f[v][u] = min(f[u][v], w)
for i in range(1, n + 1):f[i][i] = 0for k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):f[i][j] = min(f[i][k] + f[k][j], f[i][j])
# g[i][j]表示城市1的物品运输到城市j可得的利润=城市j的售价-城市i的成本-运输f[i][j]
for i in range(1, n + 1):for j in range(1, n + 1):g[i][j] = s[j] - p[i] - f[i][j]
ans = 0
for i in range(1, n + 1):# 遍历每个城市的商品now_ans = 0# 遍历移动到的城市(包括自己本身)for j in range(1, n + 1):now_ans = max(now_ans, a[i] * g[i][j])ans += now_ans # 记录每个城市的利润print(ans)

总结下解题步骤:

  1. 初始化邻接矩阵(有边直接连接的直接存,没有的存INF最大值,自己到自己的路径长度为0)
  2. 遍历(k,i,j)更新i到j的最短路,通过k
  3. 依据题意更新答案

2. Dijkstra算法

作用:处理非负权边单源最短路问题

利用贪心+动态规划思想,实现从源点s出发到所有点的最短距离

核心思想:从起点出发,每次选择距离最短的点进行”松弛”操作

算法步骤:

1.将起点入队列,d数组表示从起点s出发到达每个最短距离

2.不断取出队列中距离最小的点u,进行“松弛”:

对于从u到v,权重为w的边

dp[v] = min(dp[v], dp[u] + w)

正在更新中...

相关文章:

图论-最短路算法

1. Floyd算法 作用&#xff1a;用于求解多源最短路&#xff0c;可以求解出任意两点的最短路 利用动态规划只需三重循环即可&#xff08;动态规划可以把问题求解分为多个阶段&#xff09;定义dp[k][i][j]表示点i到点j的路径&#xff08;除去起点终点&#xff09;中最大编号不超…...

家政预约小程序05服务管理

目录 1 设计数据源2 后台管理3 后端API4 调用API总结 家政预约小程序的核心是展示家政公司提供的各项服务的能力&#xff0c;比如房屋维护修缮&#xff0c;家电维修&#xff0c;育婴&#xff0c;日常保洁等。用户在选择家政服务的时候&#xff0c;价格&#xff0c;评价是影响用…...

Django自定义命令

Django自定义命令 我们知道&#xff0c;Django内部内置了很多命令&#xff0c;例如 python manage.py runserver python manage.py makemigrations python manage.py migrate我们可以在python控制台中查看所有命令 我们也可以自定义命令&#xff0c;让python manage.py执行…...

详解VLSM技术

在现代网络设计中&#xff0c;如何高效地分配和管理IP地址是一个关键问题。传统的子网划分方法虽然简单&#xff0c;但在实际应用中常常导致IP地址的浪费。为了应对这一问题&#xff0c;VLSM&#xff08;Variable Length Subnet Mask&#xff0c;可变长子网掩码&#xff09;技术…...

面向浏览器端免费开源的三维可视化编辑器,包含BIM轻量化,CAD解析预览等特色功能。

ES 3DEditor &#x1f30d;Github地址 https://github.com/mlt131220/ES-3DEditor &#x1f30d;在线体验 https://editor.mhbdng.cn/#/ 基于vue3与ThreeJs&#xff0c;具体查看Doc 主要功能&#xff1a; 模型导入展示&#xff0c;支持OBJ、FBX、GLTF、GLB、RVT、IFC、SEA、3…...

Nacos 进阶篇---Nacos服务端怎么维护不健康的微服务实例 ?(七)

一、引言 在 Nacos 后台管理服务列表中&#xff0c;我们可以看到微服务列表&#xff0c;其中有一栏叫“健康实例数” &#xff08;如下图&#xff09;&#xff0c;表示对应的客户端实例信息是否可用状态。 那Nacos服务端是怎么感知客户端的状态是否可用呢 &#xff1f; 本章…...

【oracle004】oracle内置函数手册总结(已更新)

1.熟悉、梳理、总结下oracle相关知识体系。 2.日常研发过程中使用较少&#xff0c;随着时间的推移&#xff0c;很快就忘得一干二净&#xff0c;所以梳理总结下&#xff0c;以备日常使用参考 3.欢迎批评指正&#xff0c;跪谢一键三连&#xff01; 总结源文件资源下载地址&#x…...

建模:Maya

一、常用按键 1、alt 左键 —— 环绕查看 2、alt 中键 —— 拖动模型所在面板 3、空格 —— 进入三视图模式&#xff1b;空格 左键按住拖动 —— 切换到对应视图 二、骨骼归零 1、T Pose 旋转模式&#xff0c;点击模型&#xff0c;摆好T姿势即可 2、复制模型设置200距离…...

持续总结中!2024年面试必问 20 道 Redis面试题(四)

上一篇地址&#xff1a;持续总结中&#xff01;2024年面试必问 20 道 Redis面试题&#xff08;三&#xff09;-CSDN博客 七、Redis过期键的删除策略&#xff1f; Redis 过期键的删除策略主要涉及以下几种方式&#xff1a; 1. 定时删除&#xff08;Timed Expiration&#xff…...

Java中关于List的一些常用操作

先定义一个List&#xff0c;代码如下 //定义一个实例类 public class Model{private String id;private String code;private String name;//setter getter 方法省略}//定义一个List,赋值过程省略 List<Model> list new ArrayList<>();1.将List中每一个对象的id…...

Docker仓库解析

目录 1、Docker仓库类型2、Docker仓库的作用3、工作原理4、管理与使用最佳实践 Docker仓库是Docker生态系统中的重要组成部分&#xff0c;它是用于存储和分发Docker镜像的集中化服务。无论是公共还是私有&#xff0c;仓库都是开发者之间共享和复用容器镜像的基础。 1、Docker仓…...

开发人员容易被骗的原因有很多,涉及技术、安全意识、社会工程学以及工作环境等方面。以下是一些常见原因:

技术方面&#xff1a; 漏洞和补丁管理不当&#xff1a;未及时更新软件和依赖库可能存在已知漏洞&#xff0c;容易被攻击者利用。缺乏安全编码实践&#xff1a;没有遵循安全编码规范&#xff0c;容易引入SQL注入、跨站脚本&#xff08;XSS&#xff09;等安全漏洞。错误配置&…...

使用Python实现深度学习模型:自动编码器(Autoencoder)

自动编码器&#xff08;Autoencoder&#xff09;是一种无监督学习的神经网络模型&#xff0c;用于数据的降维和特征学习。它由编码器和解码器两个部分组成&#xff0c;通过将输入数据编码为低维表示&#xff0c;再从低维表示解码为原始数据来学习数据的特征表示。本教程将详细介…...

数据结构--树与二叉树--编程实现以孩子兄弟链表为存储结构递归求树的深度

数据结构–树与二叉树–编程实现以孩子兄弟链表为存储结构递归求树的深度 题目: 编程实现以孩子兄弟链表为存储结构&#xff0c;递归求树的深度。 ps&#xff1a;题目来源2025王道数据结构 思路&#xff1a; 从根结点开始 结点 N 的高度 max{N 孩子树的高度 1, N兄弟树的…...

Property xxx does not exist on type ‘Window typeof globalThis‘ 解决方法

问题现象 出现以上typescript警告&#xff0c;是因为代码使用了window的非标准属性&#xff0c;即原生 window 对象上不存在该属性。 解决办法 在项目 根目录 或者 src目录 下新建 xxx.d.ts 文件&#xff0c;然后进行对该 属性 进行声明即可。 注意&#xff1a;假如xxx.d.ts文…...

BOM..

区别&#xff1a;...

rust的版本问题,安装问题,下载问题

rust的版本、安装、下载问题 rust版本问题&#xff0c; 在使用rust的时候&#xff0c;应用rust的包&#xff0c;有时候包的使用和rust版本有关系。 error: failed to run custom build command for pear_codegen v0.1.2 Caused by: process didnt exit successfully: D:\rus…...

SDUT 链表9-------7-9 sdut-C语言实验-约瑟夫问题

7-9 sdut-C语言实验-约瑟夫问题 分数 20 全屏浏览 切换布局 作者 马新娟 单位 山东理工大学 n个人想玩残酷的死亡游戏&#xff0c;游戏规则如下&#xff1a; n个人进行编号&#xff0c;分别从1到n&#xff0c;排成一个圈&#xff0c;顺时针从1开始数到m&#xff0c;数到m的…...

Anthropic绘制出了大型语言模型的思维图:大型语言模型到底是如何工作

今天&#xff0c;我们报告了在理解人工智能模型的内部运作方面取得的重大进展。我们已经确定了如何在 Claude Sonnet&#xff08;我们部署的大型语言模型之一&#xff09;中表示数百万个概念。这是对现代生产级大型语言模型的首次详细了解。这种可解释性的发现将来可以帮助我们…...

网络工程师练习题

网络工程师 随着company1网站访问量的不断增加,公司为company1设立了多台服务器。下面是不同用户ping网站www.company1.com后返回的IP地址及响应状况,如图8.58所示。从图8.58可以看出,域名www.company1.com对应了多个IP地址,说明在图8.59所示的NDS属性中启用了循环功能。在…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...