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

【最短路算法】SPFA

引入

在计算机科学的世界里,算法就像是星空中的繁星,各自闪烁着智慧的光芒。它们沉默而坚定,像是一群不语的哲人,默默地解答着世界的问题。

算法的步骤,如同优美的诗行,让复杂的问题在流转的字符中得以释放。它们如同山间清泉,从一座山峰流淌到另一座山峰,涤荡着问题的尘埃,揭示出真实的面貌。

它们像是一把把钥匙,打开了通往计算机科学的大门。我们用它们来解决问题,用它们来创造奇迹。它们是我们智慧的结晶,是我们对世界的理解和对未来的憧憬。

走进这个充满算法的世界,感受那智慧的光芒和诗意的韵律。让我们一起探索未知的领域,寻找那最美的风景和最珍贵的宝藏。

算法不仅是计算机科学的基础,更是我们生活的诗意所在。它们让我们看到了未来的希望,感受到了科技的魅力。所以,让我们一起拥抱算法,让它们为我们的生活增添色彩,为我们的世界带来更多的可能性。

算法就像是计算机科学中的一道道美食佳肴,它们各自拥有独特的味道和风味。有些算法如同细腻的法式甜点,复杂而精致,需要我们耐心地逐一品味;有些算法则如同朴实的乡村面包,简单而实用,让人感到亲切和温暖。

基本介绍

而在这茫茫的算法大海中,有一种算法闪烁着亮丽的光彩——最短路算法。

最短路算法是一种图论算法,用于在加权图中找到两个节点之间的最短路径。这种算法在现实生活中有着广泛的应用,例如:

  1. 交通规划:最短路算法可以用于城市交通规划,帮助确定最短路线,以减少交通拥堵和提高交通效率。
  2. 物流配送:在物流配送中,最短路算法可以帮助确定最短路径,以最小化运输成本和时间。
  3. 网络设计:在计算机网络中,最短路算法可以帮助确定最佳路由,以确保数据包能够以最快的速度传输。
  4. 地理信息系统:在地理信息系统中,最短路算法可以用于确定两点之间的最短路径,例如在地图上查找两点之间的最佳路线。

其中,SPFA是打开图论大门的一个钥匙,就让我们走进它吧。

思路

归根结底,SPFA就是宽搜,看看就懂了。

#include <bits/stdc++.h>
using namespace std;
struct edge{int x, y, c, pre;} a[410000];int alen, last[11100];
void ins(int x, int y, int c)//ins函数的功能是建立一条从x出发到y且长度为c的边
{a[++alen] = edge{x, y, c, last[x]}; 全局增加一条有向边,并赋值last[x] = alen;                     //建立边与边的联系(都是从x出发)
}int n, m, d[11100]; //d[i]表示目前i和出发点的最短距离
bool v[11100];      //v[i]等于true表示点i在更新队列中,等于false表示点i不在更新队列中
void spfa()
{memset(d, 63, sizeof(d));d[1] = 0; //初始化d数组,出发点为1,出发点到自己的距离为0memset(v, 0, sizeof(v)); v[1] = 1; //初始化v数组,v[1]等于1,表示出发点1进入队列deque<int> Q; Q.push_back(1);   //定义更新队列,出发点进入更新队列while (!Q.empty()) //只要队列不为空,就表示还有点等着更新别的点{int x = Q.front();                     //从队列中取出准备好更新别的点的点xfor (int k = last[x]; k; k = a[k].pre) //重点理解!k首相等于和x相连的最后一条边的编号。那么倒数第二条和x相连的边的编号是多少呢?在a[k].next可以找到{int y = a[k].y;if (d[y] > d[x] + a[k].c) //尝试用x的最短距离更新y的最短距离{d[y] = d[x] + a[k].c; //如果点被更新了,那么它马上有冲动(想进更新队列)要去更新它的"亲朋好友"(与之直接相连的点)if (v[y] == 0)        //如果点y不在队列,则进入队列;如果已经在队列了,则不用再进入。{Q.push_back(y);v[y] = 1;}}}Q.pop_front(); //此时x已经更新完它的"亲朋好友",完成使命,退出队列Qv[x] = 0;      //标记x已经不再队列,以后x有可能会再次进入队列}//队列没有点等着更新别的点了,那么意味着所有点的d值都是最优的if (d[n] == d[0]) printf("-1\n"); //d[0]为初始的最大值,d[n]等于d[0]表示点n没有被更新,即点n无法到达。else              printf("%d", d[n]);
}
int main()
{scanf("%d%d", &n, &m);alen = 0;memset(last, 0, sizeof(last)); //注意构图之前一定要初始化,不然后果很严重!for (int i = 1; i <= m; i++){int x, y, c;scanf("%d%d%d", &x, &y, &c); //题目给出的是无向边,而我们的边目录是有向边ins(x, y, c);ins(y, x, c); //建立正向边、反向边}spfa();return 0;
}

详细注释都写在代码里面了,好好看。

例题 

不放了,上洛谷自己查吧.

 据说,一个欠揍的行为,需要一张图来安慰。

相关文章:

【最短路算法】SPFA

引入 在计算机科学的世界里&#xff0c;算法就像是星空中的繁星&#xff0c;各自闪烁着智慧的光芒。它们沉默而坚定&#xff0c;像是一群不语的哲人&#xff0c;默默地解答着世界的问题。 算法的步骤&#xff0c;如同优美的诗行&#xff0c;让复杂的问题在流转的字符中得以释…...

牛客网Verilog刷题——VL48

牛客网Verilog刷题——VL48 题目答案 题目 在data_en为高期间&#xff0c;data_in将保持不变&#xff0c;data_en为高至少保持3个B时钟周期。表明&#xff0c;当data_en为高时&#xff0c;可将数据进行同步。本题中data_in端数据变化频率很低&#xff0c;相邻两个数据间的变化&…...

Unity UGUI的Shadow(阴影)组件的介绍及使用

Unity UGUI的Shadow(阴影)组件的介绍及使用 1. 什么是Shadow(阴影)组件&#xff1f; Shadow(阴影)组件是Unity UGUI中的一个特效组件&#xff0c;用于在UI元素上添加阴影效果。通过调整阴影的颜色、偏移、模糊等属性&#xff0c;可以使UI元素看起来更加立体和有层次感。 2. …...

Kubernetes系列

文章目录 1 详解docker,踏入容器大门1.1 引言1.2 初始docker1.3 docker安装1.4 docker 卸载1.5 docker 核心概念和底层原理1.5.1 核心概念1.5.2 docker底层原理 1.6 细说docker镜像1.6.1 镜像的常用命令 1.7 docker 容器1.8 docker 容器数据卷1.8.1 直接命令添加1.8.2 Dockerfi…...

同步锁: synchronized

synchronized 1. synchronized的特性2. synchronized的使用3. synchronized的锁机制 1. synchronized的特性 原子性: 所谓原子性就是指一个操作或者多个操作&#xff0c;要么全部执行并且执行的过程不会被任何因素打断&#xff0c;要么就都不执行。可见性: 可见性是指多个线程…...

【微服务】springboot 多模块打包使用详解

目录 一、前言 1.1 为什么需要掌握多模块打包 二、工程模块概述 2.1 前后端不分离...

嵌入式工程师面试经常遇到的30个经典问题

很多同学说很害怕面试&#xff0c;看见面试官会露怯&#xff0c;怕自己的知识体系不完整&#xff0c;怕面试官考的问题回答不上了&#xff0c;所以今天为大家准备了嵌入式工程师面试经常遇到的30个经典问题&#xff0c;希望可以帮助大家提前准备&#xff0c;不再惧怕面试。 1&a…...

ER系列路由器多网段划分设置指南

ER系列路由器多网段划分设置指南 - TP-LINK 服务支持 TP-LINK ER系列路由器支持划分多网段&#xff0c;可以针对不同的LAN接口划分网段&#xff0c;即每一个或多个LAN接口对应一个网段&#xff1b;也可以通过一个LAN接口与支持划分802.1Q VLAN的交换机进行对接&#xff0c;实现…...

3 PostGIS基础查询

PostGIS 基础查询 数据库维护 ps aux | grep postgrespsql 使用命令登录数据库psql -U postgres -d testdb -h localhost -p 5432postgres用户名&#xff0c;testdb数据库名称&#xff0c;localhost ip地址&#xff0c;可以省略&#xff0c;5432端口&#xff0c;可以省略。 …...

Shell错误:/bin/bash^M: bad interpreter: No such file or directory

目录 错误原因和现象 解决方案 错误原因和现象 在执行shell脚本的时候&#xff0c;报错&#xff1a;/bin/bash^M: bad interpreter: No such file or directory。 是由于该脚本文件是在Windows平台编写&#xff0c;然后在MacOS平台中执行。 在Windows平台上文件是dos格式&…...

Golang之路---01 Golang的安装与配置

Golang之路—01 Golang语言安装与配置 官网上下载Windows环境下的安装包 官网下载地址 双击下载后的文件进行安装&#xff0c;可根据需要自定义选择解压后的文件位置。 接着新创建一个文件夹&#xff0c;保存Golang语言项目。 在里面新建bin,pkg,src三个文件夹。 环境变量…...

Anolis OS 8.8服务器采用docker容器方式搭建gerrit3.8.1服务

采用docker容器方式搭建gerrit3.8.1服务 一、选择管理帐户密码的方式二、部署gerrit服务1. 采用docker compose部署单服务的方式部分gerrit(1) docker-compose.yaml文件内容(2) 在docker-compose.yaml文件所在目录调用下面命令先进行初始化操作 2. 在宿主机上部署httpd服务用于…...

PyTorch 中的多 GPU 训练和梯度累积作为替代方案

动动发财的小手&#xff0c;点个赞吧&#xff01; 在本文[1]中&#xff0c;我们将首先了解数据并行&#xff08;DP&#xff09;和分布式数据并行&#xff08;DDP&#xff09;算法之间的差异&#xff0c;然后我们将解释什么是梯度累积&#xff08;GA&#xff09;&#xff0c;最后…...

Appium+python自动化(三十五)- 命令启动appium之 appium服务命令行参数(超详解)

简介 前边介绍的都是通过按钮点击启动按钮来启动appium服务&#xff0c;有的小伙伴或者童鞋们乍一听可能不信&#xff0c;或者会问如何通过命令行启动appium服务呢&#xff1f;且听一一道来。 一睹为快 其实相当的简单&#xff0c;不看不知道&#xff0c;一看吓一跳&#xf…...

vmware的window中安装GNS3

1.向vmware中的windows虚拟机传送文件 点击虚拟机-安装VMwaretools 安装在虚拟机上面 此图标代表已经成功&#xff0c;将文件复制到虚拟机上里面 2.安装 安装gns3&#xff0c;需要先安装winpcap&#xff08;检查网卡&#xff09;和wireshark&#xff08;对winpcap上数据进行抓…...

FPGA XDMA 中断模式实现 PCIE3.0 AD7606采集 提供2套工程源码和QT上位机源码

目录 1、前言2、我已有的PCIE方案3、PCIE理论4、总体设计思路和方案AD7606数据采集和缓存XDMA简介XDMA中断模式QT上位机及其源码 5、vivado工程1--BRAM缓存6、vivado工程2--DDR4缓存7、上板调试验证8、福利&#xff1a;工程代码的获取 1、前言 PCIE&#xff08;PCI Express&am…...

某某大学某学院后台Phar反序列化GetShell

觉得这个洞还算有点意思&#xff0c;可以记录一下 首先在另一个二级学院进行目录扫描时发现源码www.rar&#xff0c;并且通过一些页面测试推测这两个二级学院应该是使用了同一套CMS 分析源码&#xff0c;发现使用的是ThinkPHP 5.1.34 LTS框架 通过APP、Public得到后台访问路径…...

【ChatGPT辅助学Rust | 基础系列 | 基础语法】变量,数据类型,运算符,控制流

文章目录 简介&#xff1a;一&#xff0c;变量1&#xff0c;变量的定义2&#xff0c;变量的可变性3&#xff0c;变量的隐藏 二、数据类型1&#xff0c;标量类型2&#xff0c;复合类型 三&#xff0c;运算符1&#xff0c;算术运算符2&#xff0c;比较运算符3&#xff0c;逻辑运算…...

使用云服务器和Frp(快速反向代理)框架快速部署实现内网穿透

目录 一. 背景1.1 内网穿透1.2 Frp介绍1.3 Frp配置流程 二. 云服务器配置2.1 配置安全组2.2 编写frps.ini 三. 内网主机配置3.1 编辑frpc.ini文件3.2 启动服务并配置开机自启动 四. 参考文献 一. 背景 现在有一台ubuntu云服务器&#xff0c;我想通过内网穿透将一台内网的主机当…...

Mac 上使用 Tesseract OCR 识别图片文本

Tesseract OCR 引擎&#xff1a;Tesseract是一个开源的OCR引擎&#xff0c;你需要先安装它。可以从Tesseract官方网站&#xff08;https://github.com/tesseract-ocr/tesseract&#xff09;下载适用于你的操作系统的安装程序或源代码&#xff0c;并按照官方文档进行安装。 Tes…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...