当前位置: 首页 > 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…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

golang循环变量捕获问题​​

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

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

npm安装electron下载太慢,导致报错

npm安装electron下载太慢&#xff0c;导致报错 背景 想学习electron框架做个桌面应用&#xff0c;卡在了安装依赖&#xff08;无语了&#xff09;。。。一开始以为node版本或者npm版本太低问题&#xff0c;调整版本后还是报错。偶尔执行install命令后&#xff0c;可以开始下载…...