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

再述 Dijkstra

news 来源：原创 2025/5/22 17:43:25

再述 Dijkstra

学 Dijkstra 好久了，今天再学了一遍，感觉推翻了好多自己的知识……

定义

一种用于求非负权值的图的单源最短路径的算法。

方法

已知：如果要求从起始点 s 到某一个点 x 的最短路径，显然只能从某一个已确认为最短路径的点转移。

给个图：

假设我们的起始点是点 1，现在我们用数组记录从原点到所有点的最短路径：

1	2	3	4	5
0	$\infty$	$\infty$	$\infty$	$\infty$

由于其他点的最短路未知，故先用 $\infty$ 代替，代码中用很大的一个数字代替即可。

注意到，我们由于要求出某个点出发，所有点的最短路，显然需要更新 $n$ 次，其中 $n$ 为顶点数量。

在这 $n$ 次循环中，我们可以处理出由若干顶点组成的已知最短路集合，称之为 $K$ 。

在每次循环中，用 $O (n)$ 可以找到距离 $u(u\in K)$ 最近的那个点，更新其最短路表格，并将其加入 $K$ 中。

最后得到的结果：

1	2	3	4	5
0	5	6	7	6

证明

如何证明这种算法是对的？

假设我们有一张图：

从 $a$ 出发，求到 $e$ 的最短路径。其中 $a\rightarrow b\rightarrow e$ 这条路径已确认最短。

显然 $a\rightarrow c \rightarrow d$ 这条路径并不会比 $a\rightarrow b\rightarrow e$ 更优，且 $d\rightarrow e$ 这条边的权值一定非负（前提），所以 $a\rightarrow b \rightarrow e$ 这条路径一定是最优的。

算算时间复杂度，两层 $O (n)$ 的循环，就 $O(n^2)$ ，对于小数据可过。可允许大小约在 $n\le 10^4$ 。

优先队列优化

想想能否优化时间复杂度？

注意到，由于是要求 $n$ 个点的最短路，那么第一层的循环显然不能舍弃。

考虑优化时找到最近点的枚举步骤。

可以用一个优先队列存起来。存的东西：pair 类型，第一个元素是目前的最短路距离，第二个是点的编号。

那么众所周知，优先队列查找一个元素的时间复杂度是 $O(\log n)$ 的，其中 $n$ 为元素个数。

每次查找都是一个 $O(\log n)$ ， $n$ 次外循环，每次还要通过 $O (m)$ 的时间复杂度更新最短距离。

所以时间复杂度即为 $O((n+m)\log n)$ 。

一般来说，只要图是联通的， $m$ 基本都会比 $n$ 大，可近似为 $(m\log n)$ 。

局限性

但是，考虑到一种特殊的情况：完全图。

众所周知，完全图是一种 $m = n (n - 1)$ 的特殊图，那么优先队列优化的时间复杂度就反而退化成了 $O(n^2 \log n)$ ，反而不如朴素版。

代码

放下优先队列优化后的代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXM=5e5+5;
const int MAXN=1e4+5;
int n,m,s;
bool book[MAXN];
int dis[MAXN];
struct EDGE{int to,w,pre;
}edge[MAXM];
int head[MAXN];
priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > > heap;
void init()
{for(int i=1;i<=n;i++){dis[i]=INT_MAX;}return;
}
void add(int from,int to,int w,int num)
{edge[num].to=to;edge[num].w=w;edge[num].pre=head[from];head[from]=num;return;
}
int u,v,w;
int main(){scanf("%d%d%d",&n,&m,&s);init();dis[s]=0;for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w,i);}heap.push(make_pair(0,s));while(!heap.empty()){int t=heap.top().second;heap.pop();if(book[t]==true){continue;}book[t]=true;for(int i=head[t];i!=0;i=edge[i].pre){dis[edge[i].to]=min(dis[edge[i].to],dis[t]+edge[i].w);heap.push(make_pair(dis[edge[i].to],edge[i].to));}}for(int i=1;i<=n;i++){printf("%d ",dis[i]);}puts("");return 0;
}

再述 Dijkstra

再述 Dijkstra 学 Dijkstra 好久了，今天再学了一遍，感觉推翻了好多自己的知识…… 定义一种用于求非负权值的图的单源最短路径的算法。方法已知：如果要求从起始点 s 到某一个点 x 的最短路径，显然只能从某一个已确认为最短…...

编程日记 2025/5/22 17:43:25

大语言模型之prompt工程

前言随着人工智能的快速发展，我们正慢慢进入AIGC的新时代，其中对自然语言的处理成为了智能化的关键一环，在这个大背景下，“Prompt工程”由此产生，并且正逐渐成为有力的工具... LLM （Large Language Mode…...

编程日记 2025/5/14 6:52:10

JavaScript系列（43）--依赖注入系统实现详解

JavaScript依赖注入系统实现详解 💉 今天，让我们深入探讨JavaScript的依赖注入系统实现。依赖注入是一种设计模式，它通过将依赖关系的创建和管理从代码中分离出来，提高了代码的可维护性和可测试性。依赖注入基础概念 &#x1f…...

编程日记 2025/5/22 8:05:09

Mono里运行C#脚本36—加载C#类定义的成员变量和方法的数量

前面分析了加载类和基类的基本过程，接着来分析一下加载成员变量和方法的数量。因为我们知道C#语言定义一个类，主要就是定义成员变量，以及那些对此成员变量进行操作的方法，所以需要使用一种方法来描述C#语言定义类的能力。一般情况下，主要有两种类型：普通的类，比如前…...

编程日记 2025/5/22 17:04:55

SWPU 2022 新生赛--web题

奇妙的MD5 进入靶场然我们输入一个特殊的字符串，然后我到处翻了翻，发现有提示在MD5中有两个特殊的字符串 0e215962017 //MD5加密后弱比较等于自身 ffifdyop //MD5加密后变成万能密码这里明显就是万能密码了输入之后就来到了这个页…...

编程日记 2025/5/17 4:49:56

Windows 靶机常见服务、端口及枚举工具与方法全解析：SMB、LDAP、NFS、RDP、WinRM、DNS

在渗透测试中，Windows 靶机通常会运行多种服务，每种服务都有其默认端口和常见的枚举工具及方法。以下是 Windows 靶机常见的服务、端口、枚举工具和方法的详细说明： 1. SMB（Server Message Block） 端口 445/TCP&…...

编程日记 2025/5/22 17:01:09

记一次Linux共享内存段排除Bug：key值为0x0000000的共享内存段删除不了

本文目录一、问题情况二、解决方法2.1 通过kill命令删除2.2 通过程序删除一、问题情况今天查看共享内存段发现好多共享内存段，而且命令ipcrm -m <shmid>删除不了。回想了一下，应该是有一些程序跑while循环，或者死循环&#xff0c…...

编程日记 2025/5/21 21:30:10

RV1126画面质量四：GOP改善画质

一． 什么是 GOP GOP 实际上就是两个 I 帧的间隔，比方说分辨率是 1920 * 1080 50 帧，假设 GOP 为 5，那就是大概 2s 插入一个 I 帧。我们再回顾下，H264/H265 的帧结构。H264/H265 分别分为三种帧类型：I 帧、…...

编程日记 2025/5/20 5:52:48

手机app如何跳过无障碍权限实现弹框自动点击-ADB连接专题

手机app如何跳过无障碍权限实现弹框自动点击 --ADB连接专题一、前言我们在前期的时候，在双SIM卡进行协同外呼和SIM卡切换时，对如何在手机中“执行批处理脚本做自动点击”的内容进行预研，力图使用事件触发和坐标点击等方式来实现手机安装…...

编程日记 2025/5/22 17:32:25

kafka-保姆级配置说明(consumer)

bootstrap.servers #deserializer应该与producer保持对应 #key.deserializer #value.deserializer ##fetch请求返回时，至少获取的字节数，默认值为1 ##当数据量不足时，客户端请求将会阻塞 ##此值越大，客户端请求阻塞的时间越长&…...

编程日记 2025/5/19 0:08:56

c语言中的数组（上）

数组的概念数组是⼀组相同类型元素的集合； 数组中存放的是1个或者多个数据，但是数组元素个数不能为0。数组中存放的多个数据，类型是相同的。数组分为⼀维数组和多维数组，多维数组⼀般⽐较多⻅的是⼆维数组。数组创建在C语言…...

编程日记 2025/5/22 17:18:59

20250122-正则表达式

1. 正则标记表示一位字符：\\ 表示指定的一位字符：x 表示任意的一位字符：. 表示任意一位数字：\d 表示任意一位非数字：\D 表示任意一个字母：[a-zA-Z]（大写或小写） 表示任意一个…...

编程日记 2025/5/16 9:07:37

（回溯法子集）leetcode78

#include<iostream> #include<string> #include<vector> //只有子集需要在每个结点收集结果，其余在叶子结点收集结果 using namespace std; vector<vector<int>>ans; vector<int>combine; void backtracking(int index,vector&…...

编程日记 2025/5/22 17:39:45

Pyecharts之图表组合与布局优化

在数据可视化中，我们经常需要将多个图表组合在一起，以展示不同维度的数据或者进行对比分析。同时，合理的布局能够提升图表的可读性和用户体验。Pyecharts 提供了强大的组件和方法，让我们可以轻松实现图表的组合和布局优化。本篇将…...

编程日记 2025/5/20 8:20:41

代码随想录训练营第五十六天| 108.冗余连接 109.冗余连接II

108.冗余连接题目链接：卡码网题目链接（ACM模式） (opens new window) 讲解链接：代码随想录并查集可以解决什么问题：两个节点是否在一个集合，也可以将两个节点添加到一个集合中。引自代码随想录&#xff…...

编程日记 2025/5/22 17:34:29

私有包上传maven私有仓库nexus-2.9.2

一、上传二、获取相应文件三、最后修改自己的pom文件...

编程日记 2025/5/20 3:45:31

二叉搜索树中的搜索(力扣700)

首先介绍一下什么是二叉搜索树。二叉搜索树是一个有序树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉…...

编程日记 2025/5/19 22:44:48

社区养老服务平台的设计与实现(代码+数据库+LW)

摘要互联网发展至今，无论是其理论还是技术都已经成熟，而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播，搭配信息管理工具可以很好地为人们提供服务。针对信息管理混乱，出错率高，信息安全性差&#…...

编程日记 2025/5/19 23:47:43

高速光模块中的并行光学和WDM波分光学技术

随着AI大模型训练和推理对计算能力的需求呈指数级增长，AI数据中心的网络带宽需求大幅提升，推动了高速光模块的发展。光模块作为数据中心和高性能计算系统中的关键器件，主要用于提供高速和大容量的数据传输服务。光模块提升带宽的方法有两种…...

编程日记 2025/5/22 13:54:19

python生成图片和pdf，快速

1、下载安装 pip install imgkit pip install pdfkit2、wkhtmltopdf工具包，下载安装下载地址：https://wkhtmltopdf.org/downloads.html 3、生成图片 import imgkit path_wkimg rD:\app\wkhtmltopdf\bin\wkhtmltoimage.exe # 工具路径，安…...

编程日记 2025/5/22 16:40:17

浅谈在AI时代GIS的发展方向和建议

在AI时代，GIS（地理信息系统）的发展正经历着深刻的变革，随着人工智能技术的进步，GIS不再仅仅是传统的地图和空间数据处理工具，而是向更加智能化、自动化、精准化的方向发展。作为一名GIS开发工程师&#xff…...

编程日记 2025/5/22 16:40:17

【25考研】中科院软件考研复试难度分析！

中科院软件复试不需要上机！且对专业综合能力要求较高！提醒同学一定要认真复习！ 一、复试内容二、参考书目官方并未明确给出，建议同学参考初试书目： 1）《数据结构（C语言版）》严蔚…...

编程日记 2025/5/22 16:42:05

【2024年华为OD机试】 (A卷,200分)- 计算网络信号、信号强度（JavaScriptJava PythonC/C++）

一、问题描述题目解析问题描述我们有一个 m x n 的二维网格地图，每个格子可能是以下几种情况之一： 0：表示该位置是空旷的。x（正整数）：表示该位置是信号源，信号强度为 x。-1：表示该位置是阻隔物，信号无法直接穿透。信号源只有一个，阻隔物可能有多个。信号在传播…...

编程日记 2025/5/19 10:34:35

SpringBoot整合Swagger UI 用于提供接口可视化界面

目录一、引入相关依赖二、添加配置文件三、测试四、Swagger 相关注解一、引入相关依赖图像化依赖 Swagger UI 用于提供可视化界面： <dependency><groupId>io.springfox</groupId><artifactId>springfox-swagger-ui</artifactI…...

编程日记 2025/5/22 10:07:57

C语言：数据的存储

本文重点： 1. 数据类型详细介绍 2. 整形在内存中的存储：原码、反码、补码 3. 大小端字节序介绍及判断 4. 浮点型在内存中的存储解析数据类型结构的介绍： 类型的基本归类： 整型家族浮点家族构造类型： 指针类型&…...

编程日记 2025/5/18 6:08:48

OpenFGA

1.什么是OpenFGA Fine-Grained Authorization 细粒度关系型授权 2.什么是细粒度授权细粒度授权 (FGA) 意味着能够授予特定用户在特定资源中执行特定操作的权限。精心设计的 FGA 系统允许您管理数百万个对象和用户的权限。随着系统不断添加对象并更新用户的访问权限&#…...

编程日记 2025/5/15 14:08:28

Kafka 入门与应用实战：吞吐量优化与与 RabbitMQ、RocketMQ 的对比

前言在现代微服务架构和分布式系统中，消息队列作为解耦组件，承担着重要的职责。它不仅提供了异步处理的能力，还能确保系统的高可用性、容错性和扩展性。常见的消息队列包括 Kafka、RabbitMQ 和 RocketMQ，其中 Kafka 因其高吞吐量…...

编程日记 2025/5/17 9:19:40

单链表算法实战：解锁数据结构核心谜题——链表的回文结构

题目如下： 解题过程如下： 回文结构举例： 回文数字：12521、12321、1221…… 回文字符串：“abcba”、“abba”…… 并不是所有的循环嵌套的时间复杂度都是O(n^2) 可以用C写C程序： C里可以直接使用ListNode…...

编程日记 2025/5/17 11:59:01

【2024年 CSDN博客之星】我的2024年创作之旅：从C语言到人工智能，个人成长与突破的全景回顾

我的2024年创作之旅：从C语言到人工智能，个人成长与突破的全景回顾引言回望2024年，我不仅收获了技术上的成长，更收获了来自CSDN平台上无数粉丝、朋友以及网友们的支持与鼓励。在这条创作之路上，CSDN不仅是我展示技术成…...

编程日记 2025/5/19 19:06:33

Qt Enter和HoverEnter事件

介绍做PC开发的过程中或多或少都会接触到鼠标的悬停事件，Qt中处理鼠标悬停有Enter和HoverEnter两种事件相同点 QEvent::Enter对应QEnterEvent，描述的是鼠标进入控件坐标范围之内的行为，QEnterEvent可以抓取鼠标的位置；QEvent…...

编程日记 2025/5/20 10:49:21

Python：元组构造式和字典推导式

（Python 元组构造式和字典推导式整理笔记） 1. 元组构造式 1.1 创建元组使用圆括号： tuple1 (1, 2.5, (three, four), [True, 5], False) print(tuple1) # 输出: (1, 2.5, (three, four), [True, 5], False) 省略圆括号： tup…...

编程日记 2025/5/20 8:47:33

科普篇 | “机架、塔式、刀片”三类服务器对比

一、引言在互联网的世界里，服务器就像是默默运转的超级大脑，支撑着我们日常使用的各种网络服务。今天，咱们来聊聊服务器家族中的三位 “明星成员”：机架式服务器、塔式服务器和刀片式服务器。如果把互联网比作一座庞大的城市&…...

编程日记 2025/5/22 2:35:27

数据结构——概念与时间空间复杂度

目录前言一相关概念 1什么是数据结构 2什么是算法二算法效率 1如何衡量算法效率的好坏 2算法的复杂度三时间复杂度 1时间复杂度表示 2计算时间复杂度 2.1题一 2.2题二 2.3题三 2.4题四 2.5题五 2.6题六 2.7题七 2.8题八四空间复杂度 1题一 2题二 3…...

编程日记 2025/5/21 6:45:24

centos7 配置国内镜像源安装 docker

使用国内镜像源：由于 Docker 的官方源在国内访问可能不稳定，你可以使用国内的镜像源，如阿里云的镜像源。手动创建 /etc/yum.repos.d/docker-ce.repo 文件，并添加以下内容： [docker-ce-stable] nameDocker CE Stable -…...

编程日记 2025/5/21 16:56:11

PyCharm配置Python环境

1、打开PyCharm项目可以从File-->Open-->选择你的项目路径-->OK，或者直接点击Open，找到项目路径-->OK，如图所示(点击Ok后可能有下面的弹窗，选择“Trust Project”即可，然后选择“New Window”打开项目) …...

编程日记 2025/5/21 4:48:31

Linux（Centos、Ubuntu) 系统安装jenkins服务

该文章手把手演示在Linux系统下如何安装jenkins服务、并自定义jenkins数据文件位置、以及jenkins如何设置国内镜像源加速，解决插件下载失败问题安装方式：war包安装阿里云提供的war下载源地址：https://mirrors.aliyun.com/jenkins/war/?s…...

编程日记 2025/5/20 23:23:09

本地大模型编程实战(02)语义检索(1)

文章目录准备加载文档分割文档嵌入矢量存储查询矢量库检索返回评分先嵌入查询文本再检索检索器总结代码我们在百度、必应、谷歌等搜索引擎中使用的检索都是基于字符串的：用户输入字符串后，搜索引擎先对搜索内容进行分词，然后在已经进行了倒…...

编程日记 2025/5/19 8:12:11

使用 Redis 实现分布式锁的基本思路

使用 Redis 实现分布式锁的基本思路在分布式系统中，多个进程或服务可能会同时访问共享资源（如数据库、缓存、文件等），这可能会导致数据不一致或并发冲突。Redis 由于其高性能和单线程模型，是实现分布式锁的一个常见选…...

编程日记 2025/5/21 3:56:20

1193. 每月交易 I 表：Transactions ---------------------- | Column Name | Type | ---------------------- | id | int | | country | varchar | | state | enum | | amount | int | | trans_date | date | ---------------------- id 是这个表的主键。该表包含…...

编程日记 2025/5/19 19:23:22

【MYSQL】mysql 常用命令

文章目录 1. 数据库管理命令2. 表管理命令3. 数据操作命令4. 数据查询进阶5. 用户与权限管理6. 使用脚本操作数据库 1. 数据库管理命令 -- 查看所有数据库 SHOW DATABASES;-- 创建数据库 CREATE DATABASE 数据库名;-- 选择数据库 USE 数据库名;-- 删除数据库 DROP DATABASE 数…...

编程日记 2025/5/19 13:57:55

linux 内核学习方向以及职位

### 学习路径 1. 基础阶段： - C语言高级特性 - 指针和内存管理 - 数据结构实现 - 位操作 - 多线程编程 - Linux系统编程 - 文件I/O操作 - 进程管理 - 信号处理 - IPC机制 - Socket编程 - 必备知识 - 操作系统原理 - 计算机体系结构 - …...

编程日记 2025/5/21 22:46:03

DeepSeek火爆，参数量、激活参数和预训练 token 量是什么？

最近DeepSeek火爆，爆出了几个关键参数，分别是参数量、激活参数和预训练 token 量。这里用通俗的语言给大家解释一下~ 首先要知道1B 是 Billion（十亿）的缩写参数量：671B（6710 亿） 想象你…...

编程日记 2025/5/19 7:26:34

设计新的 Kibana 仪表板布局以支持可折叠部分等

作者：来自 Elastic Teresa Alvarez Soler, Hannah Mudge 及 Nathaniel Reese 在 Kibana 中构建可折叠仪表板部分需要彻底改造嵌入式系统并创建自定义布局引擎。这些更新改进了状态管理、层次结构和性能，同时为新的高级仪表板功能奠定了基础。我们正在开…...

编程日记 2025/5/16 21:49:10

vscode如何安装vue语法支持

在VSCode中安装Vue语法支持非常简单。1、你需要安装“Vetur”扩展，这是一个专门为Vue.js开发设计的扩展；2、你可以通过VSCode的扩展市场轻松找到并安装它；3、安装完成后，你还可以根据需要进行一些配置，以优化你的开发体…...

编程日记 2025/5/21 10:17:41

从零安装 LLaMA-Factory 微调 Qwen 大模型成功及所有的坑

文章目录从零安装 LLaMA-Factory 微调 Qwen 大模型成功及所有的坑一参考二安装三启动准备大模型文件四数据集（关键）！4.1 Alapaca格式4.2 sharegpt4.3 在 dataset_info.json 中注册4.4 官方 alpaca_zh_demo 例子 999条数据, 本机微调 5分…...

编程日记 2025/5/5 0:49:57

easyexcel-导入(读取)(read)-示例及核心部件

文章目录导入(读取)(read)-示例及核心部件导入(读取)(read)-核心部件EasyExcel(EasyExcelFactory) # 入口read() # read()方法用于构建workbook(工作簿)对象，new ExcelReaderBuilder()doReadAll()这里选XlsxSaxAnalyser这个实现类吧然后到这个类XlsxRowHandler&…...

编程日记 2025/5/17 15:16:10

10 Hyperledger Fabric 介绍

简介 HypeLedger（超级账本）是由Linux基金会2015年创建的首个面向企业应用场景的开源分布式账本平台。 HypeLedger Fabric是HypeLedger种的区块链项目之一HypeLedger Fabric引入权限管理在架构设计上支持可插拔、可扩展是首个面向联盟链场景的开源项目 …...

编程日记 2025/5/17 20:48:11

第28章测试驱动开发模式：深入绿条模式及相关技术

写在前面这本书是我们老板推荐过的，我在《价值心法》的推荐书单里也看到了它。用了一段时间 Cursor 软件后，我突然思考，对于测试开发工程师来说，什么才更有价值呢？如何让 AI 工具更好地辅助自己写代码，或许…...

编程日记 2025/5/21 14:36:21

PTMD2.0-疾病相关的翻译后修饰数据库

翻译后修饰（PTMs，post-translational modifications）通过调节蛋白质功能参与了几乎所有的生物学过程，而 PTMs 的异常状态常常与人类疾病相关。在此，PTMD 2.0展示与疾病相关的 PTMs 综合数据库，其中包含 93 …...

编程日记 2025/5/20 2:25:57

gradle生命周期钩子函数

文章目录 0. 总结表格1. 构建初始阶段gradle.settingsEvaluated()gradle.projectsLoaded() 2. 配置阶段gradle.beforeProject()gradle.afterProject()gradle.projectEvaluated()gradle.afterEvaluate()gradle.taskGraph.whenReady 3. 执行阶段gradle.taskGraph.beforeTaskgradl…...

编程日记 2025/5/21 4:45:18

再述 Dijkstra

定义

方法

证明

优先队列优化

局限性

代码

相关文章：