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

spfa()算法(求最短路)

spfa算法是对bellman_ford算法的优化,大部分求最短路问题都可以用spaf算法来求。

注意:

(1)如若图中有负权回路,不能用spfa算法,要用bellman_ford算法;若只有负权边,则可以用

spfa算法

(2)Dijikstra算法适用于图中全都是正权边

spfa算法 

step1:

初始化

step2:

取出队头结点,弹出队头,遍历队头结点的子结点,更新距离

step3:

如若第一次更新距离(st[j] == false),将结点编号加入队列。

step4:

重复循环,直至队列没有结点编号,说明到头了。

题目如下:

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 impossible

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

解答代码如下:

//主要解决三个问题:
//(1)st数组有啥用:if(st[j] == true)//提高速度//处理重边
//(2)用spfa时,为啥图中不能有负权回路:模拟一遍就会了,因为while(q.size())
//(3)为什么要用队列?
#include<iostream>
#include<cstring>
#include<queue>using namespace std;const int N = 100010;int n,m;
int e[N],ne[N],h[N],idx,w[N];
int dist[N];
bool st[N];//如st[i],记录的是编号i结点是否是在队列中void add(int a,int b,int c)
{e[idx] =b;w[idx] = c;ne[idx] = h[a];h[a] = idx;idx++;
}int spfa()
{memset(dist,0x3f,sizeof(dist));dist[1] = 0;queue<int > q;q.push(1);//队列q中存储的是上一次循环中被更新最短路径的结点编号st[1] = true;//st数组中存储的是此时编号 i 结点是否在队列中while(q.size()){int t = q.front();q.pop();//q中只存储上一次循环中被确定最短路径长的结点的编号,再上一次的会被弹出st[t] = false;for (int i = h[t];i != -1;i = ne[i]){int j =e[i];if (dist[j] > dist[t] + w[i])//通过if语句判定,说明编号 j 结点需要更新{dist[j] = dist[t] + w[i];if (!st[j])//判断q会不会出现重复的结点{q.push(j);//如果这个结点的距离是第一次被更新(初始值都是0x3f3f3f3f)//那么就进入队列,在下一次循环中,q队列中存储的就是上一次循环//更新路径长度的结点编号了st[j] = true;//标记编号 j 结点}}}}return dist[n];}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;memset(h,-1,sizeof(h));while(m--){int a,b,c;cin >> a >> b >> c;add(a,b,c);}int t = spfa();if (t == 0x3f3f3f3f)cout  << "impossible";elsecout << t;return 0;
}

 模拟过程:

  

(1) 为什么用队列?

spfa算法中使用队列是为了优化bellman_ford算法中的遍历每一条边来找到编号 结点的子结点

使用队列后,如此时t = 1,那么这一次循环中更新了 dist (第一次走到某结点时,都会更新,因为第一次走到某结点时的 dist 都是 0x3f3f3f3f )的结点就是编号 1 结点的子结点,加更新了 dist加入到队列,下次循环时,直接取出,就可以省略遍历所有边

(2)为什么不能有负权回路

(3)st数组有什么用 

我认为的作用之一就是处理重边

相关文章:

spfa()算法(求最短路)

spfa算法是对bellman_ford算法的优化&#xff0c;大部分求最短路问题都可以用spaf算法来求。 注意&#xff1a; &#xff08;1&#xff09;如若图中有负权回路&#xff0c;不能用spfa算法&#xff0c;要用bellman_ford算法&#xff1b;若只有负权边&#xff0c;则可以用 spf…...

聊聊国产数据库的生态系统建设

生态系统是指在自然界中&#xff0c;生物与环境构成统一的整体&#xff0c;之间相互影响相互制约&#xff0c;并在一定时期内处于相对稳定的动态平衡状态。所谓数据库的生态系统&#xff0c;从用户的角度看&#xff0c;就是充分打通产品使用过程中上下游的关联&#xff0c;使其…...

JDK源码解析:LinkedList

1、背景 我们咨询一下腾讯混元大模型&#xff0c;什么是“LinkedList”。 以下是混元大模型的回答&#xff1a; LinkedList 是 Java 集合框架中的一种数据结构&#xff0c;它实现了 List 和 Deque 接口。LinkedList 是一个双向链表&#xff0c;这意味着每个元素都包含对前一个和…...

drawio的问题

drawio的问题 先给出drawio的链接https://app.diagrams.net/ 我在用overleaf写论文的过程中&#xff0c;发现了一个问题&#xff0c;就是使用drawio画好图之后&#xff0c;只能保存以下几个选项&#xff1a; 但是不管是什么类型&#xff0c;在overleaf上面图片都不显示。如果…...

零基础学习Redis(3) -- Redis常用命令

Redis是一个 客户端-服务器 结构的程序&#xff0c;Redis客户端和服务器可以在同一台主机上&#xff0c;也可以在不同主机上&#xff0c;客户端和服务器之间通过网络进行通信。服务器端负责存储和管理数据。客户端则可以通过命名对服务端的数据进行操作。 Redis客户端有多种&a…...

响应式Web设计:纯HTML和CSS的实现技巧-1

响应式Web设计&#xff08;Responsive Web Design, RWD&#xff09;是一种旨在确保网站在不同设备和屏幕尺寸下都能良好运行的网页设计策略。通过纯HTML和CSS实现响应式设计&#xff0c;主要依赖于媒体查询&#xff08;Media Queries&#xff09;、灵活的布局、可伸缩的图片和字…...

FrereRTOS事件组

文章目录 一、事件组概念与操作1、事件组的概念2、事件组的操作 二、事件组函数1、创建2、删除3、设置事件4、等待事件5、同步点 三、示例&#xff1a;广播四、示例&#xff1a;等待一个任意事件五、示例: 等待多个事件都发生 学校组织秋游&#xff0c;组长在等待&#xff1a; …...

【经典算法】BFS_最短路问题

目录 1. 最短路问题介绍2. 算法原理和代码实现(含题目链接)1926.迷宫中离入口最近的出口433.最小基因变化127.单词接龙675.为高尔夫比赛砍树 3. 算法总结 1. 最短路问题介绍 最短路径问题是图论中的一类十分重要的问题。本篇文章只介绍边权为1(或边权相同)的最简单的最短路径问…...

【题目/训练】:双指针

引言 我们已经在这篇博客【算法/学习】双指针-CSDN博客里面讲了双指针、二分等的相关知识。 现在我们来做一些训练吧 经典例题 1. 移动零 思路&#xff1a; 使用 0 当做这个中间点&#xff0c;把不等于 0(注意题目没说不能有负数)的放到中间点的左边&#xff0c;等于 0 的…...

LLVM - 编译器后端-指令选择

一&#xff1a;概述 任何后端的核心都是指令选择。LLVM 实现了几种方法&#xff1b;在本篇文章中&#xff0c;我们将通过选择有向无环图&#xff08;DAG&#xff09;和全局指令选择来实现指令选择。 在本篇文章中&#xff0c;我们将学习以下主题&#xff1a; • 定义调…...

ES+FileBeat+Kibana日志采集搭建体验

1.环境准备 需要linux操作系统&#xff0c;并安装了docker环境 此处使用虚拟机演示。&#xff08;虚拟机和docker看参考我之前写的文章&#xff09; VirtualBox安装Oracle Linux 7.9全流程-CSDN博客 VirtualBox上的Oracle Linux虚拟机安装Docker全流程-CSDN博客 简单演示搭建ES…...

Dockerfile常用指令详解

Dockerfile 是一个用于定义 Docker 镜像构建过程的脚本文件&#xff0c;其中包含了一系列指令&#xff0c;用于指定如何构建和配置镜像。以下是一些常用的 Dockerfile 指令及其示例用法&#xff1a; 1. FROM 指定基础镜像&#xff0c;Dockerfile 必须以该指令开始。 示例&am…...

【vue】浏览器兼容相关

Vue.js 是一个流行的前端 JavaScript 框架&#xff0c;它支持构建单页应用和复杂的用户界面。Vue.js 的核心库本身对浏览器的支持情况如下&#xff1a; Vue.js 2.x 最低支持版本&#xff1a;IE9 及以上版本。特性支持&#xff1a;ES5。兼容性&#xff1a;Vue 2.x 在发布时就考…...

【区块链+金融服务】基于区块链的区域股权金融综合服务平台 | FISCO BCOS应用案例

区域性股权市场是我国资本市场的重要组成部分&#xff0c;是多层次资本市场体系的基石。区块链技术与区域性股权市场 分散特征天然匹配&#xff0c;从新型金融基础设施层面为场外参与各方提供公共的可信服务&#xff0c;以技术手段完善市场基础条 件&#xff0c;弥补区域性短板…...

string字符串和json对象相互转换问题

//响应体String responseStr EntityUtils.toString(response.getEntity());log.debug("下单响应码:{},响应体:{}",statusCode,responseStr);if(statusCode HttpStatus.OK.value()){JSONObject jsonObject JSONObject.parseObject(responseStr);if(jsonObject.cont…...

【生成式人工智能-十一一个不修改模型就能加速语言模型生成的方法】

一个加速语言模型生成的方法 现在语言模型的一个弊端speculative decoding预言家预测的问题 speculative decoding 模块的实现方法NAT Non-autoregressive模型压缩使用搜索引擎 一些更复杂些的speculative decoding 实现方式 speculative decoding 是一个适用于目前生成模型的加…...

Rust 错误处理

Rust 错误处理 Rust 是一种系统编程语言,以其内存安全、高并发和实用性而著称。在 Rust 中,错误处理是一个核心概念,它通过提供 Result 和 Option 类型来鼓励开发者显式地处理可能出现的错误,而不是依赖异常机制。本文将深入探讨 Rust 中的错误处理机制,包括 Result 和 O…...

程序与进程 linux系统

程序与进程 程序 &#xff08; program &#xff09;&#xff1a; 通常为 binary program &#xff0c;放置在储存媒体中&#xff08;如硬盘、光盘、软盘、磁带等&#xff09;&#xff0c; 为实体文件的型态存在&#xff1b;二进制文件&#xff0c;比如静态 /bin/date…...

使用MongoDB构建AI:Story Tools Studio将生成式AI引入Myth Maker AI游戏

Story Tools Studio利用先进的生成式AI技术&#xff0c;打造沉浸式、个性化、无穷尽的情景体验。 Story Tools Studio创始人兼首席执行官Roy Altman表示&#xff1a;“我们的旗舰游戏Myth Maker AI采用的是我们自主研发的、以AI为驱动的专家指导型故事生成器MUSE&#xff0c;它…...

鸿蒙UIAbility组件概述(二)

鸿蒙UIAbility组件概述 UIAbility组件基本用法指定UIAbility的启动页面获取UIAbility的上下文信息 UIAbility组件与UI的数据同步使用EventHub进行数据通信使用AppStorage/LocalStorage进行数据同步 UIAbility组件间交互&#xff08;设备内&#xff09;启动应用内的UIAbility启动…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

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

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