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

备战蓝桥杯---图论之最短路Bellman-Ford算法及优化

目录

上次我们讲到复杂度为(n+m)logm(m为边,n为点)的迪杰斯特拉算法,其中有一个明显的不足就是它无法解决包含负权边的图。

于是我们引进Bellman-Ford算法。

核心:枚举所有的点,能松弛就松弛,直到所有点都不能松弛。

具体过程:

我们在外循环循环n-1(n为点数),然后在内循环上枚举所有的边,能松弛就松弛。

到这里,肯定有许多人对它正确性怀疑,其实,我们可以知道,在外循环循环k轮后,k步以内可以到的点的值<=从源点在k步以内能走到的最优解(有点类似广搜)。

具体来说,当k=2时,2步以内可以到的点的值<=2步内从源点走到该点的最小距离。(<=的原因在于枚举边的时候可能会被刚刚更新的点在被更新一遍)


上次我们讲到复杂度为(n+m)logm(m为边,n为点)的迪杰斯特拉算法,其中有一个明显的不足就是它无法解决包含负权边的图。

于是我们引进Bellman-Ford算法。

核心:枚举所有的点,能松弛就松弛,直到所有点都不能松弛。

具体过程:

我们在外循环循环n-1(n为点数),然后在内循环上枚举所有的边,能松弛就松弛。

到这里,肯定有许多人对它正确性怀疑其实,我们可以知道,在外循环循环k轮后,k步以内可以到的点的值<=从源点在k步以内能走到的最优解(有点类似广搜)。

具体来说,当k=2时,2步以内可以到的点的值<=2步内从源点走到该点的最小距离。(<=的原因在于枚举边的时候可能会被刚刚更新的点在被更新一遍)

因此,在n-1轮后,因为每一个点最多被走一次(除非是负环,等下讨论),因此,利用上述结论,我们可以得出在外循环循环n-1轮后,所有的点的值为从源点出发走到的最优解。

下面我们讨论一下负环,其实,如果出现负环,最短路就应该为负无穷,我们为了判断负环,只要比较更新次数有无<=n-1即可。

因为这过于暴力,复杂度为o(n*m),基本一用就寄,于是我们考虑一下优化

我们不妨思考一个问题(这也是优化的关键)

一个点在什么情况下可以优化?

显然,只有到它的前一个点它的值优化改变后,那个点才可能被优化因为边权是不变的,而前一个点它的值无法被优化时,dis[a]=map[a][b]+dis[b],相当于dis[b]不变,那么dis[a]肯定也不变。

在知道这个后,我们让dis[源点]=0,其他为极大值。

我们对于边的枚举,只要枚举上一次被更新的点的边就可以了。

我们用队列实现(即SPFA算法,复杂度为o(k*m)(k为每一个点入队的平均次数)

还是这一题,我们用这个方法实现一下。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
struct node{int zhi;int dian;int next;
}edge[20010];
int dis[1010],head[1010],cnt,n,m1,s,t,x,y,v;
bool vis[1010];
struct ty{int dian,dis1;bool operator<(const ty &a) const{return dis1>a.dis1;}
};
void merge(int x,int y,int v){edge[++cnt].zhi=v;edge[cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
priority_queue<ty> q;
queue<int> q1;
int dij(int s,int t){q.push({s,0});while(!q.empty()){ty ck=q.top();q.pop();if(vis[ck.dian]==1) continue;vis[ck.dian]=1;for(int i=head[ck.dian];i!=-1;i=edge[i].next){int i1=edge[i].dian;if(vis[i1]==1) continue;if(dis[i1]>dis[ck.dian]+edge[i].zhi){dis[i1]=dis[ck.dian]+edge[i].zhi;q.push({i1,dis[i1]});}}}if(dis[t]>=0x3f3f3f3f) return -1;else return dis[t];
}
int spfa(int s,int t){q1.push(s);while(!q1.empty()){int hh=q1.front();vis[hh]=0;q1.pop();for(int i=head[hh];i!=-1;i=edge[i].next){int i1=edge[i].dian;if(dis[i1]>dis[hh]+edge[i].zhi){dis[i1]=dis[hh]+edge[i].zhi;if(vis[i1]==0){vis[i1]=1;q1.push(i1);}}}}if(dis[t]>=0x3f3f3f3f) return -1;else return dis[t];
}
int main(){cin>>n>>m1>>s>>t;memset(head,-1,sizeof(head));for(int i=1;i<=m1;i++){scanf("%d%d%d",&x,&y,&v);merge(x,y,v);merge(y,x,v);}memset(dis,0x3f,sizeof(dis));dis[s]=0;cout<<spfa(s,t);
}

相关文章:

备战蓝桥杯---图论之最短路Bellman-Ford算法及优化

目录 上次我们讲到复杂度为&#xff08;nm)logm(m为边&#xff0c;n为点&#xff09;的迪杰斯特拉算法&#xff0c;其中有一个明显的不足就是它无法解决包含负权边的图。 于是我们引进Bellman-Ford算法。 核心&#xff1a;枚举所有的点&#xff0c;能松弛就松弛&#xff0c;直…...

C++ //练习 5.19 编写一段程序,使用do while循环重复地执行下述任务:首先提示用户输入两个string对象,然后挑出较短的那个并输出它。

C Primer&#xff08;第5版&#xff09; 练习 5.19 练习 5.19 编写一段程序&#xff0c;使用do while循环重复地执行下述任务&#xff1a;首先提示用户输入两个string对象&#xff0c;然后挑出较短的那个并输出它。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#x…...

算法刷题:有效三角形个数

有效三角形个数 .题目链接题目详情算法原理补充知识点双指针:对撞指针 我的答案 . 题目链接 有效三角形个数 题目详情 算法原理 补充知识点 有效三角形需要满足的条件: ab>cac>bbc>a 其实在满足1的时候,c是最大的,那么2和3是显然成立的,因此我们可以这样解题: 对…...

python---变量

1.变量就是存储数据的空间&#xff0c;在内存上&#xff1b; 2.变量命名规则&#xff1a;&#xff08;1&#xff09;由数字&#xff0c;字母&#xff0c;下划线组成&#xff0c;数字不能开头&#xff1b; &#xff08;2&#xff09;不能和关键字冲突&#xff1b; &#xff08;…...

数据库第二次实验

目录 1 实验内容 2 SQL代码及运行截图 2.1 创建表并插入数据 2.1.1 创建表 2.1.2 插入数据 2.1.3 运行截图 2.2 修改表 2.2.1 SQL代码 2.2.2 运行截图 2.3 删除操作 2.3.1 SQL代码 2.3.2 运行截图 2.4 数据库的备份 2.5 数据库的恢复 1 实验内容 实验目的&#…...

容器高级知识:Kubernetes Pod 适配器模式详解

Kubernetes Pod 适配器(Adapter)模式详解 Kubernetes Pod 适配器模式是侧车&#xff08;Sidecar&#xff09;模式的一个特例&#xff0c;其中使用专用的 适配器容器 在主应用程序容器和其他服务或客户端之间 翻译 数据或信号。它充当桥梁&#xff0c;调整通信格式或协议以实现…...

云原生容器化-5 Docker常见操作命令

1.登录和退出docker仓库 使用docker login和docker logout分别用于登录和退出docker仓库。 #登录时携带用户名、密码、仓库地址信息 docker login --username test --password test123 192.168.0.22:8000 docker login --username seong --password 3er4#ER$ 192.168.0.22:8…...

几道简单的题目练一下手感

第 1 题 【 问答题 】 • 找和为K的两个元素 在一个长度为n(n < 1000)的整数序列中&#xff0c;判断是否存在某两个元素之和为k。 时间限制&#xff1a;1000 内存限制&#xff1a;65536 输入 第一行输入序列的长度n和k&#xff0c;用空格分开。 第二行输入序列中的n个整数&a…...

2023年哪个前端框架用的最多?

2023 年&#xff0c;TypeScript 的每月下载量持续稳定增长&#xff0c;年度累计下载量高达2,071,832,110&#xff08;20.7 亿&#xff09;&#xff0c;展现了强大的市场需求和用户认可。 本文来通过详细的数据&#xff08;2023 年 npm 累计下载量&#xff09;&#xff0c;看看…...

基于BitVM的乐观 BTC bridge

1. 引言 前序博客&#xff1a; 区块链互操作协议Bitcoin Bridge&#xff1a;治愈还是诅咒&#xff1f;BitVM&#xff1a;Bitcoin的链下合约 基于BitVM的乐观 BTC bridge&#xff1a; Trust-minimized two-way peg 机制 BitVM BTC bridge背后的主要思想是&#xff1a; 为比…...

谷歌浏览器安装扩展程序axure-chrome-extension

注&#xff1a; 文末附扩展附件&#xff1a;axure-chrome-extension_v0.7.0.crx 1、安装扩展程序axure-chrome-extension 找到axure-chrome-extension.crx&#xff0c;把axure-chrome-extension.crx后缀改为zip&#xff0c;然后解压&#xff0c;得到一个文件夹 2、打开谷歌浏览…...

C++学习:大小写转换

islower/isupper函数 islower和isupper是C标准库中的字符分类函数&#xff0c;用于检查一个字符是否为小写字母或大写字母。 islower和isupper函数需要包含头文件&#xff0c;也可用万能头文<bits/stdc.h>包含。 函数返回值为bool类型。 char ch1 A; char ch2 a;//…...

【王道数据结构】【chapter5树与二叉树】【P159t16】

试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似&#xff0c;指的是T1和T2都是空的二叉树或都只有一个根节点&#xff1b;或者T1的左子树和T2的左子树是相似的&#xff0c;且T1的右子树和T2的右子树是相似的 #include <iostream> #include <stack> #inc…...

代码随想录算法训练营第51天 | 139.单词拆分 多重背包理论基础

单词拆分 这道题最后是判断能否组成&#xff0c;很像回溯法的问题形式&#xff0c;和分割回文串那道题比较类似&#xff0c;所以是可以用回溯法解决的&#xff0c;但是回溯法需要使用记忆化递归来避免超时。 class Solution{ public:bool backtracking(const string s, const …...

weilai8游戏爬虫

#!/usr/bin/python # -*- coding: UTF-8 -*- #!/usr/bin/python # -*- coding: UTF-8 -*- import os,csv import re import random import time import requests from lxml import etreefrom urllib.parse import quote, unquotepage98 sess requests.Session()#创建一个sessi…...

【Java程序设计】【C00261】基于Springboot的休闲娱乐代理售票系统(有论文)

基于Springboot的休闲娱乐代理售票系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的休闲娱乐代理售票系统 本系统分为系统功能模块、管理员功能模块以及用户功能模块。 系统功能模块&#xff1a;休闲娱乐代理…...

【Linux】学习-基础IO拓展篇

Linux基础IO拓展篇—详解文件系统 理解文件系统 在Linux基础IO篇中&#xff0c;我们站在用户的视角对文件进行了理解&#xff0c;主要是针对被打开的文件&#xff0c;那么有没有没有被打开的文件呢&#xff1f;当然有&#xff01;今天我们换个视角&#xff0c;来站在系统的角…...

算法详解(力扣141——环形链表系列)

博主ID&#xff1a;代码小豪 文章目录 环形链表环形链表的性质分析快慢指针法指针的追及相遇问题 环形链表&#xff08;2&#xff09; 环形链表 先来看看环形链表的原题&#xff1a; 中间的部分叙述有点繁杂&#xff0c;简单来概括就是&#xff0c;假如有一个节点&#xff0c…...

浅谈路由器交换结构

一、路由器技术概述 路由器&#xff08;Router&#xff09;是连接两个或多个网络的硬件设备&#xff0c;在网络间起网关的作用&#xff0c;是读取每一个数据包中的地址然后决定如何传送的专用智能性的网络设备。它能够理解不同的协议&#xff0c;例如某个局域网使用的以太网协议…...

Linux第51步_移植ST公司的linux内核第3步_添加修改设备树

1、设备树文件的路径 1)、创建linux中的设备树头文件 在“my_linux/linux-5.4.31/arch/arm/boot/dts/”目录中&#xff0c;以“stm32mp15xx-edx.dtsi”为蓝本&#xff0c;复制一份&#xff0c;并命名为 “stm32mp157d-atk.dtsi”&#xff0c;这就是我们开发板的设备树头文件。…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...