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

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...