普及组集训--图论最短路径

定义:E_{u,v}表示顶点u到顶点v的一条边的权值(边权)

最短路径算法有常见的四种:floyd,dijkstra,Bellman-Ford,SPFA

不过Bellman-Ford并不常用,所以本文不提;

重点在于dijkstra,spfa;

floyd(O(n^3))

思想是对所有边进行松弛操作。

code:

for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//松弛操作 }}
}

代码解读:

可以把k理解为E_{i,j}的中转点,而后E_{i,j}=min(E_{i,j},E_{i,k}+E_{k,j})

故:\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}E_{i,j}=min(E_{i,j},E_{i,k}+E_{k,j})描述不太严谨

形象一些:

上图即为所有最短路径算法的普遍思想。

dijkstra(O(n^2+m))

把节点分为两个集合,一是以确定的出现在最短路径上的点集合,记为S;二是没确定的节点记为集合T,一开始所有点都属于T集合。其实就是著名的蓝白点思想可以去百度搜一搜。

code:

//无向图邻接矩阵存图;
for(int i=1;i<=n;i++){dis[i]=f[s][i];//dis[i]=E(s,i)
} 
for(int i=1;i<=n-1;i++){//枚举中转点 k=0;minl=0x3ffffff;//初始为无穷 for(int j=1;j<=n;j++){if(!vis[j]&&dis[j]<minl){minl=dis[j];k=j;}}if(k==0)break;//没找到中转点直接退出 vis[k]=1;//标为白点 for(int j=1;j<=n;j++){dis[j]=min(dis[j],dis[k]+f[k][j]);//松弛操作 }
}
return dis[e];//min(E(s,e))

SPFA(O(KE) or O(nm)) 

 关于复杂度:其中k为所有顶点进队的平均次数,可以证明k一般小于等于2;

SPFA就是Bellman-Ford的一种实现方式,使用了队列优化让复杂度变低

spfa也会用到松弛操作。

前置芝士:链式前向星
//用链式前向星来存图
void add(int a,int b,int c){//从a到b的一条边权为c的边 to[++cnt]=b;val[cnt]=c;nxt[cnt]=h[a];h[a]=cnt;
} 

 code:

queue<int>q;//队列
void spfa(){for(int i=1;i<=n;i++){dis[i]=0x3fffff;//初始为无穷 }dis[s]=0;vis[s]=1;q.push(s);//入队(把源点加入队列) while(!q.empty()){int u=q.front();q.pop;//弹出队列 vis[u]=0;//没被加入队列过 for(int i=h[u];~i;i=nxt[i]){//找h[u]的所有连边进行松弛操作 if(dis[u]+val[i]<dis[to[i]]){dis[to[i]]=dis[u]+val[i];//对该边进行松弛操作 if(!vis[to[i]]){//若没有加入队列 q.push(to[i]);//加入队列 vis[to[i]]=1;//标记为已经加入队列(白点) }}}}
} 

 在随机数据下spfa直接封神。

但如果不是随机数据,且有一堆特殊情况而且数据毒瘤,要设置分层图时,不要用spfa

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux内核ftrace的使用

文章目录 ftrace使用一、ftrace的功能与用途二、ftrace的实现原理三、ftrace的使用步骤1. 查看tracer&#xff1a;通过查看available\_tracers文件&#xff0c;了解当前内核中可用的插件追踪器2. 选择tracer3. 设置参数和过滤器4.开启追踪5. 读取追踪结果 四、ftrace的常用trac…

【笔记总结】华为云:应用上云后的安全规划及设计

一、背景和问题 数字化时代&#xff0c;随着信息技术的飞速发展&#xff0c;企业和各类组织纷纷将自身的应用程序迁移至云端。云计算凭借其诸多优势&#xff0c;如成本效益、可扩展性、灵活性以及便捷的资源共享等&#xff0c;已然成为了现代业务运营的重要支撑。 今年&#xf…

LeetCode-430. 扁平化多级双向链表-题解

题目链接 430. 扁平化多级双向链表 - 力扣&#xff08;LeetCode&#xff09; 题目介绍 你将得到一个双链表&#xff0c;节点包含一个“下一个”指针、一个“前一个”指针和一个额外的“子指针”。这个子指针可能指向一个单独的双向链表&#xff0c;并且这些链表也包含类似的特殊…

MySQL 慢查询日志记录 SQL优化 性能优化 日志查询 Explain

介绍 慢查询日志记录了所有执行时间超过指定参数(long_query_time&#xff0c;单位:秒&#xff0c;默认10秒)的所有SQL语句的日志。MySQL的慢查询日志默认没有开启&#xff0c;需要在MySQL的配置文件(/etc/my.cnf)中配置针对这些慢查询的SQL语句进行优化。 #开启慢查询开关 s…

【RL Application】语义分割中的强化学习方法

&#x1f4e2;本篇文章是博主强化学习&#xff08;RL&#xff09;领域学习时&#xff0c;用于个人学习、研究或者欣赏使用&#xff0c;并基于博主对相关等领域的一些理解而记录的学习摘录和笔记&#xff0c;若有不当和侵权之处&#xff0c;指出后将会立即改正&#xff0c;还望谅…

Elasticsearch 入门

Elasticsearch安装 下载软件 Elasticsearch 的官方地址:Elastic — 搜索 AI 公司 | Elastic Elasticsearch 最新的版本是 8.16.1(截止2024.11)&#xff0c;我们选择7.8.0版本。 下载地址&#xff1a;Elasticsearch 7.8.0 | Elastic Elasticsearch 分为Linux和 Windows版本&…

Pyside6-QTableView实战

使用效果 代码 import cv2 import osfrom ui.imageQuery import Ui_DialogImageQuery from utils.log_util import log_message from utils.sys_util import create_dirfrom PySide6.QtWidgets import QApplication, QDialog, QGraphicsPixmapItem, QGraphicsScene from PySid…

Redis开发03:常见的Redis命令

1.输入以下命令&#xff0c;启动redis。 sudo service redis-server start 如果你是直接安装在WSL的&#xff0c;搜索栏搜索Ubuntu或者点击左下角Windows图表找到U那一栏&#xff0c;直接打开Ubentu&#xff0c;输入账密后&#xff0c;输入“sudo service redis-server start”…

JAVA |日常开发中常见问题归纳讲解

JAVA &#xff5c;日常开发中常见问题归纳讲解 前言一、语法错误相关问题1.1 分号缺失或多余1.2 括号不匹配1.3 变量未定义或重复定义 二、数据类型相关问题2.1 数据类型不匹配2.2 整数溢出和浮点数精度问题 三、面向对象编程相关问题3.1 空指针异常&#xff08;NullPointerExc…

ubuntu的用户使用

ubuntu系统中的常规用户登录方式 在系统root用户是无法直接登录的,因为root用户的权限过大所以其安全性比较差 在登录系统时一般使用在安装系统时建立的普通用户登录 如果需要超级用户权限: Ubuntu用户密码破解 在系统安装完成后默认grub启动等待时间为0&#xff0c;建议改…

初始Python篇(6)—— 字符串

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; Python 目录 字符串的常见操作 格式化字符串 占位符 f-string 字符串的 format 方法 字符串的编码与解码 与数据验证相关的方法 …

38 基于单片机的宠物喂食(ESP8266、红外、电机)

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于STC89C52单片机&#xff0c;采用L298N驱动连接P2.3和P2.4口进行电机驱动&#xff0c; 然后串口连接P3.0和P3.1模拟ESP8266&#xff0c; 红外传感器连接ADC0832数模转换器连接单片机的P1.0~P1.…

GEE Landsat 8 可见光影像校正后下载

在遥感影像处理领域&#xff0c;Landsat 8 数据因其 30 米空间分辨率 和 多光谱波段 被广泛应用。处理这些数据时&#xff0c;研究者常常需要对数据进行裁剪、计算指数、图像增强等操作&#xff0c;以满足特定研究需求。 本文将介绍一个 Python 自动化脚本&#xff0c;使用 Goo…

Matlab Simulink HDL Coder开发流程(一)— 创建HDL兼容的Simulink模型

创建HDL兼容的Simulink模型 一、使用Balnk DUT模板二、从HDL Coder库中选择模块三、为DUT开发算法/功能四、为设计创建Testbench五、仿真验证设计功能六、Simulink模型生成HDL代码 这个例子说明了如何创建一个用于生成HDL代码的Simulink模型。要创建兼容HDL代码生成的MATLAB算法…

如何通过 JWT 来解决登录认证问题

1. 问题引入 在登录功能的实现中 传统思路&#xff1a; 登录页面时把用户名和密码提交给服务器服务器验证用户名和密码&#xff0c;并把检验结果返回给后端如果密码正确&#xff0c;则在服务器端创建 session&#xff0c;通过 cookie 把 session id 返回给浏览器 但是正常情…

像素流送api ue多人访问需要什么显卡服务器

关于像素流送UE推流&#xff0c;在之前的文章里其实小芹和大家聊过很多&#xff0c;不过今天偶然搜索发现还是有很多小伙伴&#xff0c;在搜索像素流送相关的问题&#xff0c;搜索引擎给的提示有这些。当然这些都是比较短的词汇&#xff0c;可能每个人真正遇到的问题和想获取的…

Uniad复现学习

在优云平台部署训练&#xff0c;加速训练。 关于UCloud(优刻得)旗下的compshare算力共享平台 UCloud(优刻得)是中国知名的中立云计算服务商&#xff0c;科创板上市&#xff0c;中国云计算第一股。 UCloud&#xff08;优刻得&#xff09;旗下的Compshare算力共享平台具有以下优点…

域名解析系统 DNS

1.域名系统概述 用户与互联网上某台主机通信时&#xff0c;必须要知道对方的IP地址。然而用户很难记住长达32 位的二进制主机地址。即使是点分十进制地址也并不太容易记忆。但在应用层为了便于用户记忆各种网络应用&#xff0c;连接在互联网上的主机不仅有P地址&#xff0c;而…

【软考网工笔记】网络基础理论——网络层

文章目录 中断处理过程数据包组装RIPRSVPipv4RIPv1 & RIPv2HFC 混合光纤同轴电缆&#xff08;Hybrid Fiber Coax&#xff0c;简称HFC&#xff09;BGP (边界网关协议)BGP-4 协议的四种报文ICMP 协议数字语音电子邮件协议MPLS 多协议标记交换ipv6DHCPDNS名称解析过程查询顺序…

go语言 Pool实现资源池管理数据库连接资源或其他常用需要共享的资源

go Pool Pool用于展示如何使用有缓冲的通道实现资源池&#xff0c;来管理可以在任意数量的goroutine之间共享及独立使用的资源。这种模式在需要共享一组静态资源的情况&#xff08;如共享数据库连接或者内存缓冲区&#xff09;下非 常有用。如果goroutine需要从池里得到这些资…