8 Bellman Ford算法SPFA
图论 —— 最短路 —— Bellman-Ford 算法与 SPFA_通信网理论基础 分别使用bellman-ford算法和dijkstra算法的应用-CSDN博客
图解Bellman-Ford计算过程以及正确性证明 - 知乎 (zhihu.com)
语雀版本
1 概念
**适用场景:**单源点,可以有负边,不能有负权环。
**dis(v):**源点s到v的距离。初始话dis(s)=0,其余为无穷大。
**n:**顶点数
**m:**边数
复杂度O(mn):对边进行n-1次遍历。如果dis(v)>dis(u)+e(u,v),则更新dis(v)=dis(u)+e(u,v)
**合理性:**基于这个方式,每次遍历起码有一个点的dis(v)是得到最优值。所以遍历n-1次就够了。
负权环:环的权值和为负。如果按上述的方式遍历,很有可能会导致某个点的dis值经过环之后变得更小。重复遍历后越来越小。
**判断负权环:**三角不等式。无负权环时,n-1次后所有dis都是最优。如果有,则会导致得不到最小dis。基于这一点,可以在n-1次后,再遍历一次,如果还存在dis(v)>dis(u)+e(u,v),则有负权环。
2 实现
2.1 n-1次遍历
void Bellman_Ford()
{for(int i=0;i<n;i++) dis[i]=INF;dis[0]=0;for(int i=1;i<=n-1;i++)for(int j=1;j<=m;j++)//枚举所有边{int x=u[j];//边j的起点int y=v[j];//边j的终点if(dis[x]<INF)//松弛dis[y]=min(dis[y],dis[x]+w[j]);}
}
2.2 第n次变量——三角布不等式判断环
void Bellman_Ford()
{for(int i=0;i<n;i++) dis[i]=INF;dis[0]=0;for(int i=1;i<=n-1;i++)for(int j=1;j<=m;j++)//枚举所有边{int x=u[j];//边j的起点int y=v[j];//边j的终点if(dis[x]<INF)//松弛dis[y]=min(dis[y],dis[x]+w[j]);}for(int j=1;j<=m;j++)//枚举所有边{int x=u[j];//边j的起点int y=v[j];//边j的终点if(dis[y]>dis[x]+w[j])//cout<<"有负权环";return;}
}
3 SPFA-基于队列的优化
SPFA:Shortest Path Faster Algorithm。用队列来记录待遍历的点,每次不遍历所有边,只遍历和改点相邻的边。
3.1 实现
可以用双向队列,把dis小的点放在队首,提高遍历时更新的效率(更快完成所有dis更新)struct Edge{int to,dis;
};
vector<Edge> edge[N];
bool vis[N];
int dis[N];
void SPFA(int s) {memset(dis, INF, sizeof(dis));memset(vis, false, sizeof(vis));vis[s] = true;dis[s] = 0;deque<int> Q;Q.push_back(s);while (!Q.empty()) {int x = Q.front();Q.pop_front();vis[x] = 0;for (int i = 0; i < edge[x].size(); i++) {int y = edge[x][i].to;if (dis[y] > dis[x] + edge[x][i].to) {dis[y] = dis[x] + edge[x][i].to;if (!vis[y]) {vis[y] = true;if (!Q.empty() && dis[y] < dis[Q.front()])//加入队首Q.push_front(y);else//加入队尾Q.push_back(y);}}}}
}
3.2 判断负环-判断每个点进队列的次数(大于n)
struct Edge {int from, to;int dis;Edge() {}Edge(int from, int to, int dis) : from(from), to(to), dis(dis) {}
};
struct SPFA {int n, m;Edge edges[N]; //所有的边信息int head[N]; //每个节点邻接表的头int next[N]; //每个点的下一条边int pre[N]; //最短路中的上一条弧bool vis[N];int dis[N];int cnt[N]; //进队次数void init(int n) {this->n = n;this->m = 0;memset(head, -1, sizeof(head));}void AddEdge(int from, int to, int dist) {edges[m] = Edge(from, to, dist);next[m] = head[from];head[from] = m++;}bool negativeCycle(int s) { //判负环memset(vis, false, sizeof(vis));memset(cnt, 0, sizeof(cnt));memset(dis, INF, sizeof(dis));dis[s] = 0;queue<int> Q;Q.push(s);while (!Q.empty()) {int x = Q.front();Q.pop();vis[x] = false;for (int i = head[x]; i != -1; i = next[i]) {Edge &e = edges[i];if (dis[e.to] > dis[x] + e.dis) {dis[e.to] = dis[x] + e.dis;pre[e.to] = i;if (!vis[e.to]) {vis[e.to] = true;Q.push(e.to);if (++cnt[e.to] > n)return true;}}}}return false;}
} spfa;
int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {spfa.init(n);int S;scanf("%d", &S);for (int i = 1; i <= m; i++) {int x, y, dis;scanf("%d%d%d", &x, &y, &dis);//无向边添边两次spfa.AddEdge(x, y, dis);spfa.AddEdge(y, x, dis);}spfa.negativeCycle(S);for (int i = 1; i <= n; i++)printf("%d\n", spfa.dis[i]);}return 0;
}
相关文章:
8 Bellman Ford算法SPFA
图论 —— 最短路 —— Bellman-Ford 算法与 SPFA_通信网理论基础 分别使用bellman-ford算法和dijkstra算法的应用-CSDN博客 图解Bellman-Ford计算过程以及正确性证明 - 知乎 (zhihu.com) 语雀版本 1 概念 **适用场景:**单源点,可以有负边࿰…...
nginx不允许静态文件被post请求显示405 not allowed
在单独站点的配置文件中 添加error_page 405 200 $request_uri; 即可!...
【c++笔试强训】(第三十二篇)
目录 数组变换(贪⼼位运算) 题目解析 讲解算法原理 编写代码 装箱问题(动态规划-01背包) 题目解析 讲解算法原理 编写代码 数组变换(贪⼼位运算) 题目解析 1.题目链接:数组变换__牛客网…...
shell脚本实战案例
文章目录 实战第一坑功能说明脚本实现 实战第一坑 实战第一坑:在Windows系统写了一个脚本,比如上面,随后上传到服务,执行会报错 原因: 解决方案:在linux系统touch文件,并通过vim添加内容&…...
OpenCV-图像阈值
简单阈值法 此方法是直截了当的。如果像素值大于阈值,则会被赋为一个值(可能为白色),否则会赋为另一个值(可能为黑色)。使用的函数是 cv.threshold。第一个参数是源图像,它应该是灰度图像。第二…...
lvgl9 Line(lv_line) 控件使用指南
文章目录 前言主体1. **Line 控件概述**2. **使用场景**3. **控件的样式**4. **设置点**5. **自动大小**6. **y 坐标反转**7. **事件处理**8. **示例代码** 总结 前言 在图形界面设计中,直线绘制是非常常见且重要的功能之一,尤其是在需要进行图形表示、…...
区块链概念 Web 3.0 实操
1. Web 3.0 概述 1.1 定义与背景 Web 3.0,也称为第三代互联网,是一个新兴的概念,它代表着互联网的未来发展和演进方向。Web 3.0的核心理念是去中心化、用户主权和智能化。这一概念的提出,旨在解决Web 2.0时代中用户数据隐私泄露…...
【人工智能】大数据平台技术及应用
文章目录 前言一、大数据平台基本概念及发展趋势1、数据量爆发式增长,发数据蓬勃发展2、大数据到底是什么?3、大数据处理与传统数据处理的差异4、为什么要建立大数据平台?5、大数据平台开源架构-Hadoop6、华为云大数据平台架构 二、大数据技术…...
Scala的模式匹配(7)
package hfdobject Test35 {case class Person(name:String)case class Student(name:String,className:String)//match case 能根据 类名和属性的信息,匹配到对应的类//注意://1 匹配的时候,case class的属性个数要对上//2 数学名不需要一一…...
使用 MATLAB 绘制三维散点图:根据坐标和距离映射点的颜色和大小
在数据可视化中,三维散点图是一种非常直观的方式来展示数据的分布。MATLAB 提供了强大的 scatter3 函数,可以用来绘制三维散点图,而通过调整点的颜色和大小,可以进一步增强图形的表现力。 在本篇博客中,我们将逐步讲解…...
数仓技术hive与oracle对比(五)
附录说明 附录是对测试过程中涉及到的一些操作进行记录和解析。 oracle清除缓存 alter system flush shared_pool; 将使library cache和data dictionary cache以前保存的sql执行计划全部清空,但不会清空共享sql区或者共享pl/sql区里面缓存的最近被执行的条目。刷…...
金融数学在股市交易中的具体应用
### 1. 风险管理 - **VaR(在险价值)**: VaR是衡量投资组合潜在损失的指标。例如,如果一个投资组合的VaR为100万元,置信水平为95%,这意味着在未来的一个交易日内,有95%的可能性该投资组合的损失不会超过100…...
Spring6:1 概述
Spring6:1 概述 标签 JAVASpring 目录 Spring 是什么?Spring 的狭义和广义 广义的 Spring:Spring 技术栈狭义的 Spring:Spring Framework Spring Framework 特点Spring 模块组成Spring6 特点 版本要求本课程软件版本 1. 概述 …...
Python Selenium 各浏览器驱动下载与配置使用(详细流程)
1、安装 pip install selenium 2、浏览器驱动下载 Chrome(google)浏览器驱动 下载地址:http://chromedriver.storage.googleapis.com/index.html 或 https://sites.google.com/a/chromium.org/chromedriver/home . 下载地址:http://chromedriver.stor…...
C语言期末考试——重点考点
目录 1.C语言的结构 2.三种循环结构 3.逻辑真假判断 4. printf函数 5. 强制类型转化 6. 多分支选择结构 7. 标识符的定义 8. 三目运算符 1.C语言的结构 选择结构、顺序结构、循环结构 2.三种循环结构 for、while、do-while 3.逻辑真假判断 C语言用0表示false,用非0(不…...
mongo开启慢日志及常用命令行操作、数据备份
mongo开启慢日志及常用命令行操作、数据备份 1.常用命令行操作2.mongo备份3.通过命令临时开启慢日志记录4.通过修改配置开启慢日志记录 1.常用命令行操作 连接命令行 格式:mongo -u用户名 -p密码 --host 主机地址 --port 端口号 库名; 如:连…...
Mybatis-Plus的主要API
一、实体类操作相关API BaseMapper<T>接口 功能:这是 MyBatis - Plus 为每个实体类对应的 Mapper 接口提供的基础接口。它提供了一系列基本的 CRUD(增删改查)操作方法。例如insert(T entity)方法用于插入一条记录,d…...
2023 年“泰迪杯”数据分析技能赛B 题企业财务数据分析与造假识别
2023 年“泰迪杯”数据分析技能赛B 题企业财务数据分析与造假识别 一、背景 财务数据是指企业经营活动和财务结果的数据记录,反映了企业的财务状况 与经营成果。对行业、企业的财务数据进行分析,就是要评价其过去的经营业绩、 衡量现在的财务状况、预测…...
【SpringMVC】参数传递 重定向与转发 REST风格
文章目录 参数传递重定向与转发REST风格 参数传递 ModelAndView:包含视图信息和模型数据信息 public ModelAndView index1(){// 返回页面ModelAndView modelAndView new ModelAndView("视图名");// 或// ModelAndView modelAndView new ModelAndView(…...
性能测试需求分析(超详细总结)
🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 1、客户方提出 客户方能提出明确的性能需求,说明对方很重视性能测试,这样的企业一般是金融、电信、银行、医疗器械等;他们…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
