备战蓝桥杯---图论之最短路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);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/258078.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2.16学习总结

1.邮递员送信&#xff08;dijkstra 不只是从起到到目标点&#xff0c;还要走回去&#xff09; 2.炸铁路(并查集) 3.统计方形&#xff08;数据加强版&#xff09;&#xff08;排列组合&#xff09; 4.滑雪&#xff08;记忆化&#xff09; 5.小车问题&#xff08;数学问题&#x…

枚举,#define,C中程序内存区域划分

目录 一、枚举 1.1枚举类型的声明 1.2枚举类型的优点 1.3枚举类型的使用 二、#define定义常量 三、C中程序内存区域划分 一、枚举 1.1枚举类型的声明 枚举顾名思义就是⼀⼀列举。 把可能的取值⼀⼀列举。 比如我们现实生活中&#xff1a; ⼀周的星期⼀到星期日是有限…

嵌入式培训机构四个月实训课程笔记(完整版)-Linux ARM驱动编程第三天-ARM Linux ADC和触摸屏开发 (物联技术666)

链接&#xff1a;https://pan.baidu.com/s/1V0E9IHSoLbpiWJsncmFgdA?pwd1688 提取码&#xff1a;1688 教学内容&#xff1a; 1、ADC S3C2440的A/D转换器包含一个8通道的模拟输入转换器&#xff0c;可以将模拟输入信号转换成10位数字编码。 在A/D转换时钟频率为2.5MHz时&…

【QT+QGIS跨平台编译】之四十:【gsl+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、GSL介绍二、GSL下载三、文件分析四、pro文件五、编译实践一、GSL介绍 GSL(GNU Scientific Library)是一个开源的数值计算库,用于提供一系列常用的数学函数和算法。它为科学计算和数据分析提供了高效、可靠的工具。 GSL库提供了丰富的功能,包括数值积分、数值…

数据分析基础之《pandas(8)—综合案例》

一、需求 1、现在我们有一组从2006年到2016年1000部最流行的电影数据 数据来源&#xff1a;https://www.kaggle.com/damianpanek/sunday-eda/data 2、问题1 想知道这些电影数据中评分的平均分&#xff0c;导演的人数等信息&#xff0c;我们应该怎么获取&#xff1f; 3、问题…

Compose 自定义 - 数据转UI的三阶段(组合、布局、绘制)

一、概念 组合阶段 Compisition 界面首次渲染时会将可组合函数转化为一个个布局节点 Layout Node, 使用多叉树的数据结构构建一个UI树。 布局阶段 Layout 多叉树中父节点会测量他们的子节点&#xff0c;然后在一个二维空间里进行摆放。通过从上往下测量&#xff08;如果存在子…

【C语言】Linux内核accept 系统调用代码

一、Linux 4.19内核accept 系统调用代码中文注释 /** 在使用accept时&#xff0c;我们尝试创建一个新的socket&#xff0c;与客户端建立连接&#xff0c;* 唤醒客户端&#xff0c;然后返回新的连接文件描述符&#xff08;fd&#xff09;。我们在内核空间收集* 连接方的地址&am…

C#利用接口实现选择不同的语种

目录 一、涉及到的知识点 1.接口定义 2.接口具有的特征 3.接口通过类继承来实现 4.有效使用接口进行组件编程 5.Encoding.GetBytes(String)方法 &#xff08;1&#xff09;检查给定字符串中是否包含中文字符 &#xff08;2&#xff09;编码和还原前后 6.Encoding.GetS…

NLP_Transformer架构

文章目录 Transformer架构剖析编码器-解码器架构各种注意力的应用Transformer中的自注意力Transformer中的多头自注意力Transformer中的编码器-解码器注意力Transformer中的注意力掩码和因果注意力 编码器的输入和位置编码编码器的内部结构编码器的输出和编码器-解码器的连接解…

【Web】小白友好的Java内存马基础学习笔记

目录 简介 文件马与内存马的比较 文件马原理 内存马原理 内存马使用场景 内存马分类 内存马注入方式 这篇文章主要是概念性的&#xff0c;具体技术细节不做探究&#xff0c;重点在祛魅。 简介 内存马&#xff08;Memory Shellcode&#xff09;是一种恶意攻击技术&…

抽象的问题1

vue3&#xff0c;在使用v-mode绑定属性时&#xff0c;发生了奇怪的问题&#xff0c;渲染失败了 代码如下 <template><div><form><div>账号<input v-model"form_user_Data.username" type"text"></div><div>密…

HCIA-HarmonyOS设备开发认证V2.0-3.2.轻量系统内核基础-软件定时器

目录 一、软件定时器基本概念二、软件定时器运行机制三、软件定时器状态四、软件定时器模式五、软件定时器开发流程六、软件定时器使用说明七、软件定时器接口八、代码分析&#xff08;待续...&#xff09;坚持就有收获 一、软件定时器基本概念 软件定时器&#xff0c;是基于系…

bpmn-js 事件总线处理

bpmn-js中使用EventBus作为事件的处理句柄&#xff0c;EventBus的使用和我们常规使用的事件总线没啥大的区别&#xff0c;其源码位于&#xff1a;/diagram-js/lib/core/EventBus.js &#xff08;bpmn-js使用diagram-js实现流程图的web端绘制呈现工具&#xff09;。 EventBus使用…

Kibana:如何嵌入 Kibana 仪表板

作者&#xff1a;Carly Richmond 像我这样的前端工程师经常提出的要求是将 Kibana 等来源的现有仪表板嵌入到 JavaScript Web 应用程序中。 这是我必须多次执行的任务&#xff0c;因为我们希望快速部署用户生成的视图或允许用户控制给定的视图。 从我们从精彩的开发者社区收到的…

算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

算法沉淀——BFS 解决 FloodFill 算法 01.图像渲染02.岛屿数量03.岛屿的最大面积04.被围绕的区域 BFS&#xff08;广度优先搜索&#xff09;解决 Flood Fill 算法的基本思想是通过从起始点开始&#xff0c;逐层向外扩展&#xff0c;访问所有与起始点相连且具有相同特性&#xf…

【小沐学GIS】基于WebGL绘制三维数字地球Earth(OpenGL)

&#x1f37a;三维数字地球系列相关文章如下&#x1f37a;&#xff1a;1【小沐学GIS】基于C绘制三维数字地球Earth&#xff08;456:OpenGL、glfw、glut&#xff09;第一期2【小沐学GIS】基于C绘制三维数字地球Earth&#xff08;456:OpenGL、glfw、glut&#xff09;第二期3【小沐…

B端系统从0到1:有几步,其中需求分析要做啥?

一款B系统从无到有都经历了啥&#xff0c;而其中的需求分析又要做什么&#xff1f;贝格前端工场给老铁们做一下分析&#xff0c;文章写作不易&#xff0c;如果咱们有界面设计和前端开发需求&#xff0c;别忘了私信我呦&#xff0c;开始了。 一、B端系统从0到1都有哪些要走的步骤…

ZigBee学习——BDB

✨本博客参考了善学坊的教程&#xff0c;并总结了在实现过程中遇到的问题。 善学坊官网 文章目录 一、BDB简介二、BDB Commissioning Modes2.1 Network Steering2.2 Network Formation2.3 Finding and Binding&#xff08;F & B&#xff09;2.4 Touchlink 三、BDB Commissi…

PKI - 借助Nginx 实现Https 服务端单向认证、服务端客户端双向认证

文章目录 Openssl操系统默认的CA证书的公钥位置Nginx Https 自签证书1. 生成自签名证书和私钥2. 配置 Nginx 使用 HTTPS3. 重启 Nginx 服务4. 直接访问5. 不验证证书直接访问6. 使用server.crt作为ca证书验证服务端解决方法1&#xff1a;使用 --resolve 参数进行请求域名解析解…

备战蓝桥杯---搜索(完结篇)

再看一道不完全是搜索的题&#xff1a; 解法1&#xff1a;贪心并查集&#xff1a; 把冲突事件从大到小排&#xff0c;判断是否两个在同一集合&#xff0c;在的话就返回&#xff0c;不在的话就合并。 下面是AC代码&#xff1a; #include<bits/stdc.h> using namespace …