SPFA最短路

文章目录

  • 从Bellman-Ford开始
    • 核心思想
    • 模拟算法执行过程
    • 时间复杂度
    • 模板
  • spfa
    • spfa优化的思想
    • 模板

从Bellman-Ford开始

  • 对于所有边权都大于等于0的图,任意两个顶点之间的最短路,显然不会经过重复的顶点或者边。也就是说任意一条最短路经过的定点数不会超过n个,边不会超过n-1条边
  • 而对于有边权为负的图,有可能图中会存在负环,此时途径负环的最短路没有意义。

核心思想

B e l l m a n − F o r d Bellman-Ford BellmanFord的核心思想是松弛操作,即对于边 ( u , v ) (u,v) (u,v),用 d i s t ( u ) 和 l ( u , v ) dist(u)和l(u,v) dist(u)l(u,v)的和尝试更新 d i s t ( v ) : dist(v): dist(v):
d i s t ( v ) = m i n ( d i s t ( v ) , d i s t ( u ) + l ( u , v ) ) dist(v)=min(dist(v),dist(u)+l(u,v)) dist(v)=min(dist(v),dist(u)+l(u,v))
1707988156035.png

B e l l m a n − F o r d Bellman-Ford BellmanFord所做的,就是不断尝试对图上每一条边进行松弛操作。


我们会进行多次迭代,每进行一次迭代,就对图上所有的边都尝试进行一次松弛操作,当一次迭代中没有点的 d i s t dist dist发生改变时,算法停止。


模拟算法执行过程

1707988734563.png

1707988780511.png

在每次迭代中,遍历所有边,尝试进行松弛操作

1707988890698.png

1707988875714.png


1707988959981.png

1707988972543.png


1707989035910.png

1707989051472.png

因为这里 B B B还是正无穷,还没找到从起点到 B B B的最短路,这样通过当前的 B B B更新其他点是没有意义(这也是后面 s p f a spfa spfa优化的关键)


1707989198843.png
1707989215419.png


1707989258889.png
1707989269526.png


1707989296221.png
1707989308610.png


至此第一轮迭代完成,下面是第二轮迭代

1707989412508.png

1707989457679.png

1707989517075.png

第四次迭代已经什么都更新不了了
1707989597426.png

时间复杂度

在最短路存在的情况下(图中不存在负环),由于一次迭代会使最短路的边数至少加 1 1 1,而 S S S到每个顶点的最短路经过的边数最多为 n − 1 n-1 n1,因此整个算法最多会进行 n − 1 n-1 n1轮迭代,每一轮迭代的复杂度为 O ( m ) O(m) O(m)(每条边枚举到一次),所以总的时间复杂度为 O ( n m ) O(nm) O(nm)

  • 当从 S S S点出发能到达一个负环时,就会进行n论以上的迭代

模板

int n, m;       // n表示点数,m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边,a表示出点,b表示入点,w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

spfa

spfa优化的思想

s p f a spfa spfa是通过队列来优化 b e l l m a n − f o r d bellman-ford bellmanford算法
在每一次迭代时,只有在上一次迭代中被更新了距离的点,才有可能去更新其他节点。因此,在每一次迭代时,我们将更新过距离的顶点加入一个队列(如果顶点已经在队列里则不加),在下一次迭代时,只需要遍历队列中的顶点连出去的边即可。

  • 在实际实现过程中我们不关心具体是那一次迭代。

模板

vector<vector<pii>>g(n+1);
rep(i,1,m){
	int u,v,w;
	cin>>u>>v>>w;
	g[u].pb({v,w});
	g[v].pb({u,w});
}
vector<vector<int>>inq(n+1);
vector<vector<int>>d(n+1,0x3f3f3f3f);
queue<int>q;
d[1]=0;
inq[1]=1;
q.push(1);
//跑一遍最短路
while(q.size()){
	auto t=q.front();
	q.pop();
	int u=t.x,cnt=t.y;
	inq[u]=0;
	for(auto it:g[u]){
		int v=it.x,w=it.y;
		//松弛操作,或者其他变形具体问题具体分析
		if(满足松弛){
			//更新
			if(!inq[v]){
				inq[v]=1;
				q.push(v);
			}
		}
	}
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

动态内存管理:new和delete的底层探索

之前我们在C语言上是学过malloc和calloc还要realloc等函数来在堆上获取相应的内存&#xff0c;但是这些函数是存在缺陷的&#xff0c;今天引入对new和delete的学习&#xff0c;来了解new和delete的底层实现。 首先就是在C中我们为什么要对内存进行区域的分块&#xff1f; 答案…

MyBatisPlus基础操作之增删改查

目录 一、基本使用 1.1 插入数据 1.2 删除操作 1.3 更新操作 二、条件构造器Wrapper 2.1 常用AbstractWrapper方法 2.1.1 示例一 2.2.2 示例二 2.2.3 示例三 2.2 常用QueryWrapper方法 2.2.1 示例一 2.2.2 示例二 2.2.3 示例三&#xff08;常用&#xff09; 2.3 常…

攻防演练后的一点随记

攻防演练 攻防演练算是告一段落了&#xff0c;各位红队和蓝队的兄弟们都辛苦了&#xff0c;写一点随记&#xff0c;供大家参考。 记得第一次参加攻防演练是在2018年&#xff0c;当时被派到北京&#xff0c;在某个政企单位做攻防演练支撑工作&#xff0c;然后2020年又被紧急派到…

【STM32 CubeMX】学STM必会的数据结构——环形缓冲区

文章目录 前言一、环形缓冲区是什么二、实现环形缓冲区实现分析2.1 环形缓冲区初始化2.2 写buf2.3 读buf2.4 测试 三、代码总况总结 前言 在嵌入式系统开发中&#xff0c;经常需要处理数据的缓存和传输&#xff0c;而环形缓冲区是一种常见且有效的数据结构&#xff0c;特别适用…

提前部署游戏业务防护,为何如此重要?

现在做网络游戏的企业都知道服务器的安全对于我们来说很重要&#xff01;互联网上面的DDoS攻击和CC攻击等等无处不在&#xff0c;而游戏服务器对服务器的防御能力和处理能力要求更高&#xff0c;普通的服务器则是比较注重各方面能力的均衡。 随着游戏行业的壮大&#xff0c;网络…

java 宠物在线商城系统Myeclipse开发mysql数据库web结构jsp编程servlet计算机网页项目

一、源码特点 java 宠物在线商城系统是一套完善的java web信息管理系统 servletdaobean mvc模式&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S 模式开发。开发环境为TOMCAT7.0,Myeclipse8.5开发&…

尚硅谷最新Node.js 学习笔记(三)

目录 六、Node.js 模块化 6.1、介绍 什么是模块化与模块&#xff1f; 什么是模块化项目&#xff1f; 模块化好处 6.2、模块暴露数据 模块初体验 暴露数据 6.3、导入&#xff08;引入&#xff09;模块 6.4、导入模块的基本流程 6.5、CommonJS规范 七、包管理工具 7…

站在C/C++的肩膀速通Java面向对象

默认学过C或C&#xff0c;对变量、表达式、选择、循环都会。 运行特征 解释型语言&#xff08;JavaScript、Python等&#xff09; 源文件-(平台专属解释器)->解释器中执行编译型语言&#xff08;C、Go等&#xff09; 源文件-(平台编译器)->平台可执行文件Java 源文件-(…

算法详解:滑动窗口-- 最大连续1的个数 III

题目来源:力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 本期讲解滑动窗口经典例题,我会从三个点开始讲解题目1.题目解析2.算法原理 3.编写代码 1.题目解析 这道题目理解起来还是比较简单的,我们简单分析一下,也就是给定一个数组,数组是由1和0组成…

AtCoder Beginner Contest 335 (Sponsored by Mynavi) --- F - Hop Sugoroku -- 题解

目录 F - Hop Sugoroku 题目大意&#xff1a; 思路解析&#xff1a; 代码实现&#xff1a; F - Hop Sugoroku 题目大意&#xff1a; 思路解析&#xff1a; 容易想到这是一个dp题&#xff0c;然后初始转移方程为&#xff1a; 如果当a[i] 较大时&#xff0c;时间复杂度为 O(N…

【AI视野·今日NLP 自然语言处理论文速览 第七十九期】Thu, 18 Jan 2024

AI视野今日CS.NLP 自然语言处理论文速览 Thu, 18 Jan 2024 Totally 35 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Deciphering Textual Authenticity: A Generalized Strategy through the Lens of Large Language Semantics …

MySQL数据库-MVCC多版本并发控制

mvcc,多版本并发控制&#xff08;Multi-Version Concurrency Control&#xff09;,是一种用于数据库管理系统中的并发控制方法. 在传统的并发控制方法中,如锁定机制,当一个事务修改数据时,会对相关的数据对象进行锁定,其他事务需要等待该锁释放才能进行操作。这种方法存在着事…

操作系统-408

一、操作系统概述 1、定义 负责协调软件和硬件的计算机资源的工作为上层应用提供简易的服务操作系统是系统软件 2、功能&#xff1a; 操作系统是系统资源的管理者 处理机管理存储器管理文件管理设备管理向上层提供方便易用的服务 命令接口程序接口对硬件机器的扩展 3、特征…

详解tomcat中的jmx监控

目录 1.概述 2.如何开启tomcat的JMX 3.tomcat如何实现JMX的源码分析 1.概述 本文是博主JAVA监控技术系列文章的第二篇&#xff0c;前面一篇文章中我们介绍了JAVA监控技术的基石——jmx&#xff1a; 【JMX】JAVA监控的基石-CSDN博客 本文我们将从使用和源码实现两个方面聊…

springboot743二手交易平台

springboot743二手交易平台 获取源码——》公主号&#xff1a;计算机专业毕设大全

Python面向对象学习小记——面向过程VS面向对象

【面向过程就好比你是一个工人&#xff0c;你得亲自去做一个个任务 面向对象就好比你一个包工头&#xff0c;你可以差遣你下面的工人去做】

日期类运算符重载以及const成员详细解析

个人主页&#xff1a;点我进入主页 专栏分类&#xff1a;C语言初阶 C语言进阶 数据结构初阶 Linux C初阶 算法 欢迎大家点赞&#xff0c;评论&#xff0c;收藏。 一起努力&#xff0c;一起奔赴大厂 目录 一.前言 二.运算符重载 2.1概念 2.2比较的符号重载 2.2.1…

linux 安装docker

目录 环境 操作步骤 1 下载脚本 2 执行脚本 3 检查docker版本&#xff0c;证明安装成功 环境 阿里云 ubuntu 22.04 64位 操作步骤 参考linux系统安装docker-腾讯云开发者社区-腾讯云 (tencent.com) 1 下载脚本 curl -fsSL https://get.docker.com -o get-docker.sh …

JavaWeb学习|Filter与ThreadLocal

学习材料声明 所有知识点都来自互联网&#xff0c;进行总结和梳理&#xff0c;侵权必删。 引用来源&#xff1a;尚硅谷最新版JavaWeb全套教程,java web零基础入门完整版 Filter 1、Filter 过滤器它是 JavaWeb 的三大组件之一。三大组件分别是&#xff1a;Servlet 程序、Liste…

RH850从0搭建Autosar开发环境【2X】- Davinci Configurator之XCP模块配置详解(上)

XCP模块配置详解 - 上 一、XCP模块配置项处理1.1 Tx Pdu配置项二、XCP模块其他配置项2.1 参数XcpMainFunctionPeriod2.2 参数XcpOnCanEnabled2.3 容器XcpOnCan总结从本节开始先专注与配置项错误处理以及构建Autosar Rh850的最小系统搭建。 XCP模块在汽车电子各控制器中处于十分…