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

8 Bellman Ford算法SPFA

news 来源：原创 2025/5/9 12:53:02

图论 —— 最短路 —— 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 概念 **适用场景：**单源点，可以有负边&#xff0…...

编程日记 2025/5/9 12:53:02

Oracle篇—11gRAC安装在linux7之后集群init.ohasd进程启动不了报错CRS-0715问题

💫《博主介绍》：✨又是一天没白过，我是奈斯，DBA一名✨ 💫《擅长领域》：✌️擅长Oracle、MySQL、SQLserver、阿里云AnalyticDB for MySQL(分布式数据仓库)、Linux，也在扩展大数据方向的知识面✌️…...

编程日记 2025/5/5 1:06:07

[golang][MAC]Go环境搭建+VsCode配置

一、go环境搭建 1.1 安装SDK 1、下载go官方SDK 官方：go 官方地址中文：go 中文社区根据你的设备下载对应的安装包： 2、打开压缩包，根据引导一路下一步安装。 3、检测安装是否完成打开终端，输入： go ve…...

编程日记 2025/5/9 11:57:05

【乐企文件生成工程】搭建docker环境，使用docker部署工程

1、自行下载docker 2、自行下载docker-compose 3、编写Dockerfile文件 # 使用官方的 OpenJDK 8 镜像 FROM openjdk:8-jdk-alpine# 设置工作目录 WORKDIR ./app# 复制 JAR 文件到容器 COPY ../lq-invoice/target/lq-invoice.jar app.jar # 暴露应用程序监听的端口 EXPOSE 1001…...

编程日记 2025/5/8 8:06:56

关于数据库数据国际化方案

方案一：每个表设计一个翻译表数据库国际化的应用场景用到的比较少，主要用于对数据库的具体数据进行翻译，在需要有大量数据翻译的场景下使用，举个例子来说，力扣题目的中英文切换。参考方案可见： https://b…...

编程日记 2025/5/9 2:50:36

【目标跟踪】Anti-UAV数据集详细介绍

Anti-UAV数据集是在2021年公开的专用于无人机跟踪的数据集，该数据集采用RGB-T图像对的形式来克服单个类型视频的缺点，包含了318个视频对，并提出了相应的评估标准（the state accurancy, SA)。文章链接：https://arxiv.…...

编程日记 2025/5/9 12:26:22

第10章大模型的有害性（下）

在本章中，我们继续探讨大型语言模型（LLM）可能带来的有害影响，重点讨论有毒性（toxicity）和虚假信息（disinformation）。这些影响不仅影响用户的体验，也可能对社会产生深远的…...

编程日记 2025/5/9 12:42:48

DevOps工程技术价值流：GitLab源码管理与提交流水线实践

在当今快速迭代的软件开发环境中，DevOps（开发运维一体化）已经成为提升软件交付效率和质量的关键。而GitLab，作为一个全面的开源DevOps平台，不仅提供了强大的版本控制功能，还集成了持续集成/持续交付(CI/CD)…...

编程日记 2025/5/9 12:22:13

Qt 面试题学习11_2024-11-29

Qt 面试题 1、什么是Qt事件循环 ？2、纯虚函数和普通的虚函数有什么区别3、Qt 的样式表是什么？ 1、什么是Qt事件循环 ？ Qt事件循环是一种程序架构，它用于处理窗口系统和其他用户界面事件，以及与用户界面无关的事件例如…...

编程日记 2025/5/9 3:36:37

云原生和数据库哪个好一些？

云原生和数据库哪个好一些？云原生和数据库各有其独特的优势，适用于不同的场景。云原生强调高效资源利用、快速开发部署和高可伸缩性，适合需要高度灵活性和快速迭代的应用。而数据库则注重数据一致性、共享和独立性，确保数据的稳定…...

编程日记 2025/5/9 12:37:41

baomidou Mabatis plus引入异常

1 主要异常信息 Error creating bean with name dataSource 但是有个重要提示 dynamic-datasource Please check the setting of primary 解决方法：增加 <dependency><groupId>com.baomidou</groupId><artifactId>dynamic-datasource-sp…...

编程日记 2025/5/9 12:08:42

Oracle篇—通过官网下载最新的数据库软件或者历史数据库软件

编程日记 2025/5/6 22:43:46

初学git报错处理 | 从IDEA远程拉取、创建分支中“clone failed”“couldn‘t checkout”

1.远程拉取“clone failed” 我新建了一个文件夹，结果clone failed。后来发现，原来是在这个文件夹里没有建立本地仓库。打开文件夹，右键git bush，然后键入git init,就可以成果clone啦！ 2.新建分支“couldnt checkou…...

编程日记 2025/5/9 12:06:30

【趣味】斗破苍穹修炼文字游戏HTML,CSS,JS

目录图片展示游戏功能扩展功能完整代码实现一个简单的斗破苍穹修炼文字游戏，你可以使用HTML、CSS和JavaScript结合来构建游戏的界面和逻辑。以下是一个简化版的游戏框架示例，其中包含玩家修炼的过程、增加修炼进度和显示经验值的基本功能。图片…...

编程日记 2025/5/8 14:28:32

Luban数据插件的用法

配置后数据后，点击图1中的gen.bat文件启动生成配置数据和解析配置数据代码的程序，自动生成配置数据和解析用到的代码；因为我已经指定了生成内容的输出路径为Unity项目的路径下面，所以，不用再搬运生成的内容到项目目录…...

编程日记 2025/5/9 12:17:00

「Mac畅玩鸿蒙与硬件35」UI互动应用篇12 - 简易日历

本篇将带你实现一个简易日历应用，显示当前月份的日期，并支持选择特定日期的功能。用户可以通过点击日期高亮选中，还可以切换上下月份，体验动态界面的交互效果。关键词 UI互动应用简易日历动态界面状态管理用户交互一、功能说明…...

编程日记 2025/5/9 12:22:13

BiGRU：双向门控循环单元在序列处理中的深度探索

一、引言在当今的人工智能领域，序列数据的处理是一个极为重要的任务，涵盖了自然语言处理、语音识别、时间序列分析等多个关键领域。循环神经网络（RNN）及其衍生结构在处理序列数据方面发挥了重要作用。然而，传统的 RN…...

编程日记 2025/5/7 12:32:40

sscanf与sprintf函数

本期介绍🍖 主要介绍：sscanf()、sprintf()这对输入/输出函数，并详细讲解了这两个函数的应用场景。概述🍖 在C语言的输出和输入库中，有三对及其相似的库函数：printf()、scanf()、fprintf()、fscanf()、spri…...

编程日记 2025/5/9 12:25:21

工业智能网关在该企业中的应用实践

随着工业4.0时代的到来，智能制造已成为企业转型升级的重要方向。工业智能网关作为工业互联网架构中的关键组件，正逐步在各大企业中发挥重要作用。本文将以某制造企业为例，详细探讨天拓四方工业智能网关在该企业中的应用实践，展现其…...

编程日记 2025/5/9 12:15:55

python毕业设计常见的一些开源库！

作为一个Python开发者，在开发过程中经常会使用到各种工具库来简化工作、提高效率。以下是一些常见的Python开发工具库及其介绍和官方链接。序号库名称功能介绍官方链接或参考网址1numpy提供高效的多维数组操作和数学函数，是许多数据科学和科学计算任务的…...

编程日记 2025/5/9 11:18:47

编程语言中什么是框架？什么是Cocoa?Foundation.framework的底层实现?Swift如何引入ObjC框架?

编程语言中什么是框架？ 在编程语言中，框架（Framework）是一种特定的软件库，它提供了一套预先定义的代码和组件，用于加速和简化特定类型的应用程序的开发。框架通常提供了一套标准化的开发工具集和约定&#…...

编程日记 2025/5/9 12:03:25

C++ 游戏开发入门

一、为什么选择 C 进行游戏开发 C 在游戏开发领域具有独特的地位。它兼具高效性与对底层硬件的良好控制能力，这使得它非常适合开发对性能要求极高的游戏核心引擎部分。许多知名的大型游戏，如《使命召唤》系列、《虚幻竞技场》等，其底层架构都…...

编程日记 2025/4/29 3:51:41

【娱乐项目】基于cnchar库与JavaScript的汉字查询工具

Demo介绍利用了 cnchar 库来进行汉字相关的信息查询，并展示了汉字的拼音、笔画数、笔画顺序、笔画动画等信息用户输入一个汉字后，点击查询按钮，页面会展示该汉字的拼音、笔画数、笔画顺序，并绘制相应的笔画动画和测试图案 cnchar…...

编程日记 2025/5/7 8:34:52

20241129解决在Ubuntu20.04下编译中科创达的CM6125的Android10出现找不到库文件libncurses.so.5的问题

20241129解决在Ubuntu20.04下编译中科创达的CM6125的Android10出现找不到库文件libncurses.so.5的问题 2024/11/29 21:11 缘起：中科创达的高通CM6125开发板的Android10的编译环境需要。 vendor/qcom/proprietary/commonsys/securemsm/seccamera/service/jni/jni_if.…...

编程日记 2025/5/9 11:41:41

自然语言处理：基于BERT预训练模型的中文命名实体识别（使用PyTorch）

命名实体识别（NER） 命名实体识别（Named Entity Recognition, NER）是自然语言处理（NLP）中的一个关键任务，其目标是从文本中识别出具有特定意义的实体，并将其分类到预定义的类别中。这…...

编程日记 2025/5/9 11:13:27

记录一次用php 调用ai用stream返回

直接写代码了 config 里面是配置文件就不写了，这样要去不同的平台申请去写一个 service,解释一下代码写了两个ai，一个是星火，一个是质谱，他们都是调用curl 方法，并返回数据， s t r e a m 为假就是等等返…...

编程日记 2025/5/9 11:25:59

vue引入并调用electron插件在网页报错Dynamic require of “electron“ is not supported

报错信息 Error: Dynamic require of "electron" is not supported 这个错误信息表明你正在尝试在一个普通的网页环境中动态地引入(electron)，但是这是不被允许的。Electron是一个用于构建桌面应用程序的框架，它结合了Node.js和Chromium&#…...

编程日记 2025/5/9 11:06:18

【C++】数组

1.概述所谓数组，就是一个集合，该集合里面存放了相同类型的数据元素。数组特点： （1）数组中的每个数据元素都是相同的数据类型。 （2）数组是有连续的内存空间组成的。 2、一维数组 2.1维数组定…...

编程日记 2025/5/9 12:53:02

Python 中的 try-except 语句介绍

Python 中的 try-except 语句介绍在编程过程中，异常处理是非常重要的一部分。Python 提供了 try-except 语句来捕获和处理程序运行时可能出现的异常。本文将详细介绍 try-except 语句的基本概念、常见错误类型以及一些实用的代码示例。 1. try-except 语句的基本…...

编程日记 2025/5/7 5:21:30

网络原理-初识

1.网络的发展历程独立模式独立模式：计算机之间相互独立。每个终端A、B、C各自持有客户端数据网络互连随着时代的发展，越来越需要计算机之间互相通信，共享软件和数据，即可以多个计算机协调工作来完成业务，就有…...

编程日记 2025/5/4 11:21:30

uniapp动态表单

使用了uniapp自带扩展组件和uv-ui组件库自行安装下载 <template><view class"assetEdit_container"><view class"type-box"><uv-formlabelPosition"left"labelWidth"140rpx":model"formData"ref"…...

编程日记 2025/4/23 0:11:41

基于智能语音交互的智能呼叫中心工作机制

在智能化和信息化不断进步的现代，智能呼叫中心为客户提供高质量、高效率的服务体验，提升众多品牌用户的满意度和忠诚度。作为实现智能呼叫中心的关键技术之一的智能语音交互技术，它通过集成自然语言处理（NLP）、语音识别…...

编程日记 2025/5/9 3:50:33

flask的第一个应用

本文编写一个简单的实例来记录下flask的使用文章目录简单实例flask中的路由无参形式有参形式参数类型不同的http方法本文小结简单实例 flask的依赖包都安装好之后，我们就可以写一个最简单的web应用程序了，我们把这个应用程序命名为first.py: from fl…...

编程日记 2025/5/9 7:48:53

macOS开发环境配置与应用开发

macOS开发环境配置与应用开发在数字化时代，软件开发已成为推动各行各业创新的重要引擎。macOS，作为苹果公司推出的操作系统，以其强大的性能、优雅的用户界面和丰富的开发工具，吸引了无数开发者的目光。本文将深入探讨macOS开发环…...

编程日记 2025/5/9 11:47:50

【SpringBoot】整合篇

1、log4j2 第一步，导入依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web</artifactId> <exclusions> <exclusion> <…...

编程日记 2025/5/9 11:20:48

Vue实战技巧：如何展示附件（PDF、MP4、Excel、Zip等）并修改名称下载

大家好，今天给大家分享一篇关于在Vue项目中展示附件（PDF、MP4、Excel、Zip等）并修改名称下载的教程。在实际开发过程中，这个功能非常实用，下面我们就一起来学习一下。一、准备工作首先，确保你的项目中已经…...

编程日记 2025/5/8 15:57:31

多线程运行时，JVM（Java虚拟机）的内存模型

在多线程运行时，JVM（Java虚拟机）的内存模型主要涉及以下几个方面： 1. 主内存和工作内存 JVM内存模型定义了主内存和工作内存的概念。主内存是所有线程共享的内存区域，而工作内存是每个线程私有的内存区域。线程对变量…...

编程日记 2025/5/9 12:40:49

VS与SQL Sever（C语言操作数据库）

作者这里使用的是程序是： Visual Studio SQL Sever (1 对VS的操作 1.首先我们打开Visual Studio Installer，并以管理员身份运行 2.点击修改 3.先选择数据存储和处理，再在右方添加处理工具&#…...

编程日记 2025/5/9 12:23:14

一次奇妙的getshell之旅

1. 资产收集时发现一个网站： https://xxxxxxxxxx/ischool/publish_page/0/ 发现存在管理员登陆: 这里之前在该旁站找到一个SQL注入，然后找到的这个账户密码（这里如何从SQL注入找到账户密码前借鉴前面的报告。）： 账号&…...

编程日记 2025/5/9 12:36:40

C# 集合（Collection）

文章目录前言一、动态数组（ArrayList）二、哈希表（Hashtable）三、排序列表（SortedList）四、堆栈（Stack）五、队列（Queue）六、点阵列（BitArray&…...

编程日记 2025/5/6 6:49:03

深度学习模型：门控循环单元（GRU）详解

本文深入探讨了门控循环单元（GRU），它是一种简化版的长短期记忆网络（LSTM），在处理序列数据方面表现出色。文章详细介绍了 GRU 的基本原理、与 LSTM 的对比、在不同领域的应用以及相关的代码实现，…...

编程日记 2025/5/9 9:19:04

深入浅出：开发者如何快速上手Web3生态系统

Web3作为互联网的未来发展方向，正在逐步改变传统互联网架构，推动去中心化技术的发展。对于开发者而言，Web3代表着一个充满机遇与挑战的新领域，学习和掌握Web3的基本技术和工具，将为未来的项目开发提供强大的支持。那么…...

编程日记 2025/5/9 11:12:26

HCIA笔记6--路由基础与静态路由：浮动路由、缺省路由、迭代查找

文章目录 0. 概念1.路由器工作原理2. 跨网访问流程3. 静态路由配置4. 静态路由的应用场景4.1 路由备份4.2 浮动路由4.3 缺省路由 5. 迭代路由6 问题6.1 为什么路由表中有的下一跳的地址有接口？6.2 个人电脑的网关本质是什么？ 0. 概念自治系统&#xff…...

编程日记 2025/5/9 12:09:43

【北京迅为】iTOP-4412全能版使用手册-第三十二章网络通信-TCP套字节

iTOP-4412全能版采用四核Cortex-A9，主频为1.4GHz-1.6GHz，配备S5M8767 电源管理，集成USB HUB,选用高品质板对板连接器稳定可靠，大厂生产，做工精良。接口一应俱全，开发更简单,搭载全网通4G、支持WIFI、蓝牙、…...

编程日记 2025/5/5 13:42:47

图片预处理技术介绍4——降噪

图片预处理大家好，我是阿赵。这一篇将两种基础的降噪算法。之前介绍过均值模糊和高斯模糊。如果从降噪的角度来说，模糊算法也算是降噪的一类，所以之前介绍的两种模糊可以称呼为均值降噪和高斯降噪。不过模糊算法对原来的图像特征的…...

编程日记 2025/5/6 14:58:58

Java基础面试题12：Java中的两种异常类型是什么？它们有什么区别？

在 Java 中，异常是非常重要的一部分。理解异常的种类和它们的区别，是每个 Java 开发者都需要掌握的基础技能。 Java 中的异常分类 Java 中异常的根本来源是 Throwable 类，它包含了两大类：错误（Error）和异常…...

编程日记 2025/5/9 12:37:41

MySQL5.6升级MySQL5.7

升级方式介绍 08 数据库服务版本升级方法 5.6 – 5.7 – 8.0 数据库版本升级方法： Inplace-本地升级步骤一：在同一台服务器中，需要部署高版本数据库服务实例步骤二：低版本数据库中的数据进行备份迁移，迁移到高版本…...

编程日记 2025/5/9 12:15:55

Pytorch实现心跳信号分类识别(支持LSTM,GRU,TCN模型）

Pytorch实现心跳信号分类识别(支持LSTM,GRU,TCN模型） 目录 Pytorch实现心跳信号分类识别(支持LSTM,GRU,TCN模型） 1. 项目说明 2. 数据说明 （1）心跳信号分类预测数据集 3. 模型训练 （1）项目安装 &…...

编程日记 2025/5/9 12:07:42

走进科学json版：在 JSON 格式中，字符串值必须使用双引号 “ 来界定，而不能使用单引号 ‘

走进科学疑难问题出现在调试fastapi程序的时候，报错碰到422错误 INFO: 192.168.0.99:46536 - "POST /v1/chat/completions/ HTTP/1.1" 422 Unprocessable Entity 干净利索，只有这一句报错，不管代码里加入多少print语句查看…...

编程日记 2025/5/9 1:27:18

【C#】书籍信息的添加、修改、查询、删除

文章目录一、简介二、程序功能2.1 Book类属性：方法： 2.2 Program 类三、方法：四、用户界面流程：五、程序代码六、运行效果一、简介简单的C#控制台应用程序，用于管理书籍信息。这个程序将允许用户添加、编辑、查看…...