图论------贝尔曼-福德(Bellman-Ford)算法
算法概述:
Bellman-Ford算法核心代码如下
for(int i = 1;i<=n-1;i++)
for(int j = 1;j<=m;j++)
if(dic[v[j]]> dic[u[j]] + w[j]]
dic[v[j]] = dic[u[j]] + w[j];
首先我们要了解一个点就是我们这次不再使用邻接矩阵来存储图的信息,而是定义三个一维数组来存储图的信息。
首先定义 u[n] 来存储边的起点,v[n]来存储边的终点,w[n]来存储边的长(权重)。
例如存储如下元素
4 4
1 2 3
2 4 7
3 4 5
3 1 3

和Dijkstra算法一样,这段代码也是求单源最短路径,所以我们同样也要定义一个dic[n]数组来存储所有点到1的最短距离。注意,这里因为使用的并非邻接矩阵,所以初始化dic时默认除了dic[1] = 0以外,暂时全部看作不连通,也就是假设以以上数据为例,dic内容要初始化为
【0 ,inf, inf, inf】,其中inf看作无穷大,表示不通。
那么我们再来看核心代码的最后两句。
if(dic[v[j]]> dic[u[j]] + w[j]]
dic[v[j]] = dic[u[j]] + w[j];
dic[v[j]]的值是1 到 v[j]这个点的值, dic[u[j]] 是 1 到 u[j] 这个点的值 , w[j] 是 u[j] 到 v[j] 的值,意思是如果如果 1 通过 1 -> u[j] -> v[j] 这条路比 1 -> v[j] 值小的话,更新dic[v[j]]的值。也就是通过u[j] ->v[j] 这条边进行松弛来优化路径。
初始化示意图如下:

for(int i = 1;i<=n-1;i++)
for(int j = 1;j<=m;j++)
if(dic[v[j]]> dic[u[j]] + w[j]]
dic[v[j]] = dic[u[j]] + w[j];
当第一轮循环时:
当先通过 j = 1 通过第一条边进行优化时, if(dic[ 2 ] > dic[ 1 ] + 3],发现dic[2 ] 需优化,然后
重置 dic[2] = dic[1]+3 = 3。
当 j = 2 时 通过第二条边进行优化时, if(dic[ 4 ] > dic[ 2 ] + 7],发现dic[4] 可以优化,然后
重置 dic[ 4 ] = dic[ 2 ] + 7 = 3+7 = 10。
当 j = 3时,通过第三条边进行优化时,if(dic[ 4 ] > dic[ 3 ] + 5],发现dic[4]无法优化,因为
dic[ 4 ] = 10 < dic[ 3 ] + 5 =inf + 5。
当 j = 4 时 通过第四条边进行优化时, if(dic[ 1 ] > dic[ 3 ] + 3],发现dic[1]无法优化,因为
dic[ 1 ] = 0 < dic[ 3 ] + 3 =inf + 3。
最后经过一轮松弛后得到 dic = [0, 3, inf ,10];

当 i= 2 进行第二轮松弛时,
当先通过 j = 1 通过第一条边进行优化时, if(dic[ 2 ] > dic[ 1 ] + 3],发现dic[2 ] 无需优化,因为 dic[2] = dic[1]+3 = 3。
当 j = 2 时 通过第二条边进行优化时, if(dic[ 4 ] > dic[ 2 ] + 7],发现dic[4] 无需优化
当 j = 3时,通过第三条边进行优化时,if(dic[ 4 ] > dic[ 3 ] + 5],发现dic[4]无需优化
当 j = 4 时 通过第四条边进行优化时, if(dic[ 1 ] > dic[ 3 ] + 3],发现dic[1]无需优化
这样我们就完成了这组数据,因为这是构建的有向图,所以1 才无法到达 3.
既然很清晰流程了 我再丢给大家一组数据:
5 7
1 2 8
1 3 1
1 4 2
3 4 2
2 4 3
3 5 3
4 5 3
现在请找到一张草稿纸来试着执行刚才所讲的流程。
具体代码:
#include<stdio.h>
int main(void)
{
int u[10], v[10], w[10];
int n, m, inf = 99999999;
int dic[10] = { 0 };
scanf_s("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf_s("%d%d%d", &u[i], &v[i], &w[i]);//存储边的信息
for (int i = 2; i <= n; i++)
dic[i] = inf;//初始化1 的单源最短路径值。
//核心代码
for (int i = 1; i <= n - 1; i++)
for (int j = 1; j <= m; j++)
if (dic[v[j]] > dic[u[j]] + w[j])
dic[v[j]] = dic[u[j]] + w[j];
for (int i = 1; i <= n; i++)
printf("%d ", dic[i]);//输出结果
}
注意事项:
最外层代码循环n-1次的原因是,n 个顶点,1到任何顶点的最多经过n-1个顶点。每一轮松弛循环如果没有完成单源最短路径的最终结果,都至少会有一次松弛。
细心的同学可能会发现我们刚才使用的数据:
5 7
1 2 8
1 3 1
1 4 2
3 4 2
2 4 3
3 5 3
4 5 3
是上一篇文章的内容,在上一篇中结果是:0 5 1 2 4 。
而在这里答案是:0 8 1 2 4。
那么为什么会造成这种影响呢,因为我们使用的这段代码是处理有向图的,而在上一篇文章中是处理无向图的,那么有没有什么办法来改进这段代码使代码能够处理无向图呢?答案当然是可以的,而且十分简单。
聪明的同学注意到数据
4 4
1 2 3
2 4 7
3 4 5
3 1 3
在第二轮就能发现没有优化证明已经得出结果,每必要进行n-1轮循环,那么大家思考下,怎么提前退出循环呢?
课后作业:
改进这段代码使代码能够处理无向图。
如何证明达到最优解提前退出循环。
明天带来答案。
相关文章:
图论------贝尔曼-福德(Bellman-Ford)算法
算法概述: Bellman-Ford算法核心代码如下 for(int i 1;i<n-1;i) for(int j 1;j<m;j) if(dic[v[j]]> dic[u[j]] w[j]] dic[v[j]] dic[u[j]] w[j]; 首先我们要了解一个点就是我们这次不再使用邻接矩阵来存储图的信息,而是定义三个一维数组来…...
带你彻底搞懂useLayoutEffect的使用场景
开篇第一句: useLayoutEffect 可能会影响性能。尽可能使用 useEffect。 useLayoutEffect 是 useEffect 的一个版本,在浏览器重新绘制屏幕之前触发。 使用方法 useLayoutEffect(setup, dependencies?)调用 useLayoutEffect 在浏览器重新绘制屏幕之前进行布局测量&…...
大厂进阶之二:React高级用法HOC、Hooks对比、异步组件
本文分文三部分: HOC高阶组件 higher order componentHooks 16.8版本后新增的钩子API异步组件使用lazy和suspense两个api实现组件代码打包分割和异步加载 一、HOC高阶组件 1、定义 高阶组件不是组件而是函数,是react中用于复用组件逻辑的高级技巧&am…...
【扒代码】ope.py
文件目录: 引用方式 if not self.zero_shot: # 非零样本情况下,计算边界框的宽度和高度 box_hw torch.zeros(bboxes.size(0), bboxes.size(1), 2).to(bboxes.device) box_hw[:, :, 0] bboxes[:, :, 2] - bboxes[:, :, 0] # 宽度 box_hw[:, :, 1] bbox…...
【Rust光年纪】探索Rust终端编程:从跨平台操作到用户界面设计
构建跨平台终端应用的完美选择:Rust 库综述 前言 随着终端应用程序的发展,越来越多的开发者开始寻找跨平台的、易于使用的库来构建终端用户界面和执行终端操作。本文将介绍几个流行的 Rust 库,它们提供了丰富的功能和灵活的 API 来满足不同…...
67、ceph
一、ceph 1.1、ceph概念 ceph是一个开源的,用c语言写的分布式的存储系统。存储文件数据。 /dev/sdb fdisk /dev/sdb gdisk /dev/sdb lvm 逻辑卷 可以扩容 raid 磁盘阵列 高可用 基于物理意义上的单机的存储系统。 分布式有多台物理磁盘组成一个集群&…...
最大正方形[中等]
优质博文:IT-BLOG-CN 一、题目 在一个由0和1组成的二维矩阵内,找到只包含1的最大正方形,并返回其面积。 示例 1: 输入:matrix [["1","0","1","0","0"],[&quo…...
JavaScript 浅谈观察者模式 前端设计模式
2、观察者模式 2.1、观察者模式 2.1.1、前言 定义一种一对多的依赖关系,当一个对象发生变化时,所有依赖于它的对象都会自动收到通知并更新。 两个角色: Subject(主题/被观察者) Observer(观察者&…...
【自动驾驶】自定义消息格式的话题通信(C++版本)
目录 新建消息文件更改包xml文件中的依赖关系更改cmakelist文件中的配置执行时依赖改变cmakelist编译顺序发布者程序调用者程序新建launch文件程序测试 新建消息文件 在功能包目录下,新建msg文件夹,下面新建mymsg.msg文件,其内容为 string …...
提升前端性能的JavaScript技巧
1. 前端JavaScript性能问题 前端JavaScript的性能问题可以显著影响Web应用的用户体验和整体性能。以下是一些常见的前端JavaScript性能问题: 1.1. 频繁的DOM操作 问题描述:JavaScript经常需要与DOM(文档对象模型)交互来更新页面内容。然而,每次DOM操作都可能触发浏览器的…...
“服务之巅:Spring Cloud中SLA监控与管理的艺术“
标题:“服务之巅:Spring Cloud中SLA监控与管理的艺术” 在微服务架构中,服务调用的可靠性和性能是至关重要的。服务级别协议(Service Level Agreement,简称SLA)是衡量服务性能的关键指标,它定义…...
ChatGPT角色定位提问提示词和指令完整版
角色定位提问 在与ChatGPT的对话中,角色定位提问是一种有效的策略,通过为ChatGPT和自己设定特定的角色或身份,可以引导对话朝着更加具体、有针对性的方向发展。这种提问方式不仅有助于ChatGPT更好地理解问题的背景和需求,还能使回…...
docker之我不会的命令
docker命令之我不会的 保存镜像(打包) docker save 镜像名或镜像id -o 保存路径和镜像名字例子: docker save tomcat -o /home/my_tomcat.tar加载保存的镜像 docker load -i 镜像保存的位置例子 在/home/路径下 docker load -i my_tomca…...
Together规则引擎 金融解决方案
目录 1.金融法规和期望正在发生变化,快速跟踪您的金融数字化变革!2.抵押贷款功能集(MFS)3.MFS 示例模型4.MFS 知识特点5.MFS特定功能 1.金融法规和期望正在发生变化,快速跟踪您的金融数字化变革! ogether规则引擎使金融机构能够简…...
【PyQt5】PyQt5 主要类
1.经常使用的模块 Sr.No.模块描述1QtCore其他模块使用的核心非GUI类2QtGui图形用户界面组件3QtMultimedia低级多媒体编程的类4QtNetwork网络编程的类5QtOpenGLOpenGL支持类6QtScript用于评估Qt脚本的类7QtSql使用SQL进行数据库集成的类8QtSvg用于显示SVG文件内容的类9QtWebKit…...
渗透测试实战-HFS远程RCE漏洞利用
免责声明:文章来源于真实渗透测试,已获得授权,且关键信息已经打码处理,请勿利用文章内的相关技术从事非法测试,由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失,均由使用者本…...
企业级管理系统模板 -- 若依
文章目录 前言一、若依模板运行效果二、若依模板下载地址 1、版本说明2、前端下载地址3、后端下载地址三、修改模板代码名称四、修改前端标题及logo总结 前言 在我们学习别人的项目时,总会遇到许多不同的管理系统,例如:学生管理系统…...
无人车搭载无人机技术详解
无人车搭载无人机技术,是近年来智能交通与无人机技术深度融合的产物,旨在通过集成两者的优势,实现更加灵活、高效的作业能力。该技术将无人机作为无人车的一个可移动、多功能的传感器平台或执行器,通过协同工作,扩展无…...
从“抠图”到“抠视频”,Meta上新AI工具SAM 2。
继2023年4月首次推出SAM,实现对图像的精准分割后,Meta于北京时间2024年7月30日推出了能够分割视频的新模型SAM 2(Segment Anything Model 2)。SAM 2将图像分割和视频分割功能整合到一个模型中。所谓“分割”,是指区别视…...
一篇讲清楚什么是密码加密和加盐算法 | 附Java代码实现
目录 前言: 一、密码加密 1. MD5介绍 2.彩虹表攻击 3.测试复杂密码是否能被攻破 二、加盐算法 1.对密码123456演示加盐算法 2.盐值的储存 3.密码加盐思想总结 三、Java代码实现 前言: 早些年,数据泄露屡见不鲜,每个班上总…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
