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

Acwing Bellman-Ford SPFA

1. Bellman-Ford

该算法适用于有负权边的情况,注意:如果有负权环的话,最短路就不一定存在了。时间复杂度 O ( m n ) . O(mn). O(mn).该算法可以求出来图中是否存在负权回路,但求解负权回路,通常用SPFA算法,而不用Bell-Ford算法,因为前者的时间复杂度更低。

Bellman-ford不要求用邻接表或者邻接矩阵存储边,为简化操作,可以定义一个结构体,存储a,b,w。表示存在一条边a点指向b点,权重为w。则遍历所有边时,只要遍历全部的结构体数组即可

主要步骤:

  • 循环n次:循环的次数的含义:假设循环了k次则表示:从起点经过不超过k条边,走到某个点的最短距离
  • 每次循环,遍历图中的所有的边。对每条边(a,b,w),(指的是从a点到b点,权值是w的一条边)更新d[b] = min(d[b],d[a]+w)。该操作称为松弛操作。
  • 该算法能够保证,在循环n次后,对所有的边(a,b,w),都满足d[b] <= d[a] + w。这个不等式被称为三角不等式。

ACwing 853. 有边数限制的最短路
在这里插入图片描述

实现思路:

  • 利用上述的Bellman-ford算法
  • 依旧定义一个距离数组dist,初始化未正无穷(0x3f3f3f3f)。注意最后判断到n号节点是否有路径不是直接判断dist[n] == 0x3f3f3f3f,因为存在负权边,可能更新的时候会存在dist[n] = 0x3f3f3f3f - c,即无穷大加上一个负数,仍为无穷大但数值还是改变了,所以最后有路径的判断改为dist[n] > 0x3f3f3f3f / 2.
  • 本题要求1号到n号点不超过k条边的最短距离,则循环k次来寻找最短路;
  • 每次再遍历m条边,判断加入当前点后,各店点到起点的距离是否变小,若变小则更新距离;
  • 注意:该距离更新时可能会导致参与的边的数量大于k,因此应在每次遍历前设置一个备份数组backup,记录在k次遍历中,本次遍历的上一次的距离数组状态,在该次遍历中对每条边的距离数组更新时采用备份数组,确保本次更新范围在当前的边数限制内。

具体实现代码:`

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 510, M = 10010;int n, m, k; // n: 顶点数, m: 边数, k: 最多使用的边数
int dist[N], backup[N]; // dist: 存储当前节点的最短距离,backup: 每轮备份上一轮的最短距离// 定义一个结构体存储边的信息
struct Edge {int a, b, w; // a: 起点, b: 终点, w: 边的权重
} edges[M]; // 存储所有的边,最多 M 条// Bellman-Ford 算法的核心函数,返回 1 到 n 的最短距离
int bellman_ford() {// 初始化距离数组,将所有点的距离设置为一个非常大的值(无穷大)memset(dist, 0x3f, sizeof dist);dist[1] = 0; // 源点(起点)1到自己的距离为 0// Bellman-Ford 算法允许最多使用 k 条边来放松所有边for (int i = 0; i < k; i++) { // 执行 k 轮松弛操作memcpy(backup, dist, sizeof dist); // 将当前距离备份// 遍历每条边,尝试更新目标顶点的最短距离for (int j = 0; j < m; j++) {int a = edges[j].a, b = edges[j].b, w = edges[j].w; // 获取边的起点,终点和权重dist[b] = min(dist[b], backup[a] + w); // 更新顶点 b 的距离}}// 如果最终 dist[n] 的值仍然非常大,说明无法在 k 条边以内到达顶点 nif (dist[n] > 0x3f3f3f3f / 2) return -1; // 0x3f3f3f3f 是表示无穷大的近似值return dist[n]; // 返回最短路径距离
}int main() {cin >> n >> m >> k; // 读取顶点数 n, 边数 m 和最多可用边数 k// 读取每条边的起点、终点和权重,并存入 edges 数组for (int i = 0; i < m; i++) {int a, b, w;cin >> a >> b >> w;edges[i] = {a, b, w};}// 调用 bellman_ford 函数计算最短路径int t = bellman_ford();// 如果 t 返回 -1 且 dist[n] 不是 -1(没有负权环),输出 "impossible"if (t == -1 && dist[n] != -1) puts("impossible"); else cout << t << endl; // 否则输出最短路径的距离return 0;
}

2.SPFA

  • 若要使用SPFA算法,一定要求图中不能有负权回路。只要图中没有负权回路,都可以用SPFA,即也可以求解正权边的题,这个算法的限制是比较小的。时间复杂度一般为 O ( m ) , O(m), O(m)最差为 O ( m n ) . O(mn). O(mn).在一些情况下可以代替Dijkstra算法

  • SPFA其实是对Bellman-Ford的一种优化,相比Bellman-Ford判环的时间复杂度也更低。 它优化的是这一步:d[b] =
    min (d[b],d[a] + w)

  • 我们观察可以发现,只有当d[a]变小了,在下一轮循环中以a为起点的点(或者说a的出边)就会更新,即下一轮循环必定更新d[b]。

  • 考虑用一个队列queue,来存放距离变小的节点(当图中存在负权回路时,队列永远都不会为空,因为总是存在某个点,在一次松弛操作后,距离变小)。

具体实现代码(详解版):

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 100010;int e[N], ne[N], idx, w[N], h[N]; // e: 邻接点, ne: 下一条边的索引, 
//idx: 当前边的索引, w: 边的权重, h: 头节点int dist[N]; // 存储从起点 1 到每个节点的最短距离
int n, m; 
bool s[N]; // 记录节点是否在队列中,避免重复入队// 添加一条从 a 到 b 的边,权重为 c 的边
void add(int a, int b, int c) {e[idx] = b; // 终点 bne[idx] = h[a]; // 将边 idx 加到节点 a 的邻接表中w[idx] = c; // 边的权重h[a] = idx++; // 更新节点 a 的头指针,指向新加的边
}// SPFA 算法求解最短路径
int spfa() {memset(dist, 0x3f, sizeof dist); // 初始化距离为无穷大dist[1] = 0; // 起点 1 到自己的距离为 0queue<int> q; // 定义队列用于处理节点q.push(1); // 将起点 1 入队s[1] = true; // 标记起点 1 已入队// 队列不为空时进行循环while (q.size()) {auto t = q.front(); // 取出队首节点q.pop(); // 弹出队首节点s[t] = false; // 标记节点 t 不在队列中// 遍历节点 t 的所有邻接边for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i]; // 获取节点 t 的邻接点 j// 如果从节点 t 到 j 的路径更短,则更新 j 的距离if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];// 如果节点 j 不在队列中,则将其加入队列if (!s[j]) {s[j] = true; // 标记节点 j 已入队q.push(j); // 节点 j 入队}}}}// 如果终点 n 的距离仍然为无穷大,表示无法到达,返回 -1if (dist[n] > 0x3f3f3f3f / 2) return -1;else return dist[n]; // 否则返回最短距离
}int main() {cin >> n >> m; // 输入节点数 n 和边数 mmemset(h, -1, sizeof h); // 初始化头节点数组为 -1,表示没有边// 读取每条边的信息,并调用 add 函数将其加入邻接表while (m--) {int a, b, w;cin >> a >> b >> w;add(a, b, w);}// 调用 spfa 函数计算最短路径int t = spfa();// 如果最短距离为 -1,且终点距离不为 -1,则输出 "impossible"if (t == -1 && dist[n] != -1) puts("impossible");else cout << t << endl; // 否则输出最短路径的距离return 0;
}

相关文章:

Acwing Bellman-Ford SPFA

1. Bellman-Ford 该算法适用于有负权边的情况&#xff0c;注意&#xff1a;如果有负权环的话&#xff0c;最短路就不一定存在了。时间复杂度 O ( m n ) . O(mn). O(mn).该算法可以求出来图中是否存在负权回路&#xff0c;但求解负权回路&#xff0c;通常用SPFA算法&#xff0c…...

我能禁止使用某协议的ip禁止访问我的资源吗

是的&#xff0c;你可以禁止使用某个协议的IP地址访问你的资源。这种操作通常涉及网络防火墙、服务器配置或应用程序设置&#xff0c;具体方法取决于你的网络环境和使用的技术。以下是一些常见的实现方法&#xff1a; 1. 使用防火墙 大多数防火墙&#xff08;硬件或软件&…...

快速理解TCP协议(二)——TCP协议中的拥塞控制机制详解

在计算机网络中&#xff0c;TCP&#xff08;传输控制协议&#xff09;是一种广泛使用的面向连接的、可靠的、基于字节流的传输层通信协议。TCP协议通过一系列复杂的机制来确保数据的可靠传输&#xff0c;其中拥塞控制是至关重要的一环。本文将深入探讨TCP协议中的拥塞控制机制&…...

Linux:debug: systemtap: ubacktrace

https://docs.huihoo.com/systemtap/sourceware.org/systemtap/SystemTap_Beginners_Guide/ustack.html 这个函数可以帮助将user level的backtrace打印出来。 stap -d /bin/ls --ldd \ -e probe process("ls").function("xmalloc") {print_usyms(ubacktra…...

使用AI进行需求分析的案例研究

生成式 AI 的潜在应用场景似乎无穷无尽。虽然这令人兴奋&#xff0c;但也可能让人不知所措。因此&#xff0c;团队在使用这项技术时需要有明确的目标&#xff1a;关键是要明确生成式 AI 在团队工作中能产生哪些实质性影响。 在软件工程中&#xff0c;一个引人注目的应用场景是…...

Python内置的re库

Python内置的re库是专门用于处理正则表达式的标准库。它提供了一系列函数和类&#xff0c;使得在Python程序中可以使用正则表达式进行字符串的搜索、替换、分割等操作。re库的使用非常广泛&#xff0c;几乎任何需要复杂文本处理的场景都可以用到它。 主要函数 1、complie函数…...

毕业设计选题:基于ssm+vue+uniapp的面向企事业单位的项目申报小程序

开发语言&#xff1a;Java框架&#xff1a;ssmuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;M…...

jQuery 简介⑤属性操作

九、属性操作 jQuery的属性操作方法一览表 $("selector").val(); // 获取第一个匹配元素的value值(一般用于表单控("selector").val("Hello"); // 设置所有匹配元素的value值为"Hello" $("selector").html();// 获取第一个…...

[Linux] Linux操作系统 进程的状态

标题&#xff1a;[Linux] Linux操作系统 进程的状态 个人主页&#xff1a;水墨不写bug &#xff08;图片来源于网络&#xff09; 目录 一、前置概念的理解 1.并行和并发 2.时间片 3.进程间具有独立性 4.等待的本质 正文开始&#xff1a; 在校的时候&#xff0c;你一定学过《…...

深入解析Python 中的 sortedcontainers 库:高效的排序数据结构

在日常的 Python 编程中&#xff0c;列表&#xff08;list&#xff09;、集合&#xff08;set&#xff09;和字典&#xff08;dict&#xff09;是常用的数据结构。然而&#xff0c;在某些特定的场景下&#xff0c;我们需要对数据进行排序&#xff0c;并且希望在插入、删除或访问…...

什么是服务器日志,日志有什么作用?

前言 服务器日志是指服务器等电脑设备或软件的运作记录‌。这些日志记录了服务器接收客户端处理请求的过程以及服务器对这些请求的处理结果。服务器日志对于排查和解决计算机系统和网络应用中的问题至关重要&#xff0c;因为它们包含了用于调试问题的消息、服务器状态以及其他…...

Codeforces Round 971 (Div. 4)A-G1题解

Codeforces Round 971 (Div. 4) A 就是b - a #include <bits/stdc.h> #define int long longusing namespace std;void solve() {int a, b;cin >> a >> b;cout << b - a << endl; }signed main() {ios::sync_with_stdio(false);cin.tie(0);co…...

QT----基于QML的计时器

赶上了实习的末班车,现在在做QML开发,第一天的学习成果,一个计时器.逻辑挺简单的,纯QML实现,代码在仓库,可以对比文档和提交记录学习起来更清晰 QT-Timer 学习使用c的listmodel 学习使用了如何用c的listmodel来存储数据. 新建一个TImeListModel类继承自QAbstractListModel c…...

Stable Diffusion的高分辨率修复(Hires.fix)

Stable Diffusion的高分辨率修复&#xff08;Hires.fix&#xff09;是一项重要的功能&#xff0c;它旨在提高生成图像的分辨率和细节&#xff0c;从而使画面变得更加清晰和精细。以下是关于Stable Diffusion高分辨率修复&#xff08;Hires.fix&#xff09;的详细解释&#xff1…...

智慧体育馆可视化:实时监控与智能管理

利用图扑可视化技术实现对体育馆的实时监控和数据分析&#xff0c;提升运营效率、观众体验和安全管理水平&#xff0c;打造智能化场馆环境。...

【NLP】基于“检测器-纠错器”中文文本纠错框架

前言 许多方法将中文拼写纠正&#xff08;检测和纠正给定中文句子中的错误字符&#xff09;视为序列标注任务&#xff0c;并在句子对上进行微调。一些方法使用错误检测器作为初步任务&#xff0c;然后将检测结果用于辅助后续的错误纠正过程。然而&#xff0c;现有方法在使用检…...

vue 中加载 Mapbox GL JS Examples

Mapbox GL JS 示例 1. Mapbox GL JS的基础使用2. style 的使用2.1. 切换 style2.2. 配置一个第三方 style &#xff08;添加一个Layer&#xff09;2.3. 配置一个带有 slot 的 style2.4. 创建一个自定义 style 的 layer 类实现 WebGL 内容2.5. 添加Marker2.6. 添加 geojson 格式…...

Vue3 中组件传递 + css 变量的组合

文章目录 需求效果如下图所示代码逻辑代码参考 需求 开发一个箭头组件&#xff0c;根据父组件传递的 props 来修改 css 的颜色 效果如下图所示 代码逻辑 代码 父组件&#xff1a; <Arrow color"red" />子组件&#xff1a; <template><div class&…...

秋分之际,又搭建了一款微信记账本小程序

在这个金色的季节里&#xff0c;每一粒粮食都蕴含着生命的奇迹&#xff0c;每一片叶子都在诉说着成长的故事。秋分之际&#xff0c;又搭建了一款微信记账本小程序。 产品概述 微信记账本小程序是一款便捷的个人财务管理工具&#xff0c;旨在帮助用户轻松记录、管理和分析日常…...

聚合函数count 和 group by

count函数&#xff1a; count&#xff08;列名&#xff09; SELECT COUNT(sid) FROM grade 统计列中所有的数值个数&#xff0c;会忽略null值。 count&#xff08;*&#xff09;和count&#xff08;1&#xff09; SELECT COUNT(*) FROM grade SELECT COUNT(1) FROM grade 统…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

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

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

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...