当前位置: 首页 > 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;这就是我们开发板的设备树头文件。…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...