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

Dijkstra算法解析

news 来源：原创 2025/5/14 23:42:49

Dijkstra算法，用于求解图中从一个起点到其他所有节点的最短路径。解决单源最短路径问题的有效方法。

条件

有向

带权路径

时间复杂度 O（n平方）

方法步骤

1 把图上的点分为两个集合要求的起点和除了起点之外的点。能直达的写上权值不能直达的写上无穷自己到自己的距离是0

2 在除起点以外的中找权值最小的顶点，这个顶点加入起点所在的集合。由于新顶点的并入，可以把新顶点作为中转点，再重新计算起点到所有除已经并入顶点的距离，找最小的继续并入，直到所有顶点并入起点所在的集合。

以下是对代码的详细解析和注释：

代码解析

全局变量定义

#define N 1005 // 定义最大顶点数为1005
int n, m; // n表示顶点数，m表示边数
bool str[N]; // 用于标记是否已确定最短路径
int dis[N]; // 存储从起始点到各个顶点的最短距离
int g[N][N]; // 邻接矩阵，存储图的结构

N：定义图中最大顶点数为1005。
n 和 m：分别表示图中的顶点数和边数。
str：布尔数组，用于标记某个顶点是否已经确定了最短路径。
dis：数组，存储从起点到每个顶点的最短距离。
g：邻接矩阵，g[i][j] 表示从顶点 i 到顶点 j 的距离。

Dijkstra算法实现

void dijkstra() {// 初始化dis数组为一个很大的值（这里选择0x3f3f3f3f）memset(dis, 0x3f3f3f3f, sizeof(dis));// 起始点到自身的距离为0dis[1] = 0;for (int i = 1; i <= n; ++i) {int temp = -1; // 选择未确定的顶点// 寻找当前未确定的最小距离顶点for (int j = 1; j <= n; ++j)if (!str[j] && (temp == -1 || dis[j] < dis[temp]))temp = j;// 更新与该顶点相邻的其他顶点的距离for (int j = 1; j <= n; ++j)dis[j] = min(dis[j], dis[temp] + g[temp][j]);// 标记该顶点已经确定了最短路径str[temp] = true;}// 输出结果for (int i = 1; i <= n; ++i) {if (dis[i] == 0x3f3f3f3f)cout << "-1" << " "; // 如果没有到该顶点的路径则输出-1elsecout << dis[i] << " "; // 否则输出最短距离}
}

初始化：
- memset(dis, 0x3f3f3f3f, sizeof(dis));：将 dis 数组初始化为一个很大的值（0x3f3f3f3f），表示初始时从起点到其他顶点的距离是无穷大。
- dis[1] = 0;：将起点到自身的距离设置为0。
主循环：
- for (int i = 1; i <= n; ++i)：循环 n 次，每次找到一个未确定最短路径的顶点。
- int temp = -1;：初始化当前未确定的最短距离顶点为 -1。
- for (int j = 1; j <= n; ++j)：遍历所有顶点，找到未确定最短路径的顶点中距离最短的顶点 temp。
  - if (!str[j] && (temp == -1 || dis[j] < dis[temp]))：如果顶点 j 未确定最短路径且距离更短，则更新 temp。
- for (int j = 1; j <= n; ++j)：更新与顶点 temp 相邻的其他顶点的距离。
  - dis[j] = min(dis[j], dis[temp] + g[temp][j]);：如果通过 temp 到达 j 的距离更短，则更新 dis[j]。
- str[temp] = true;：标记顶点 temp 已经确定了最短路径。
结果输出：
- 遍历 dis 数组，输出从起点到每个顶点的最短距离。
- 如果 dis[i] 仍然是 0x3f3f3f3f，表示没有路径到达顶点 i，输出 -1。
- 否则输出 dis[i]。

主函数

int main() {// 初始化邻接矩阵g为一个很大的值memset(g, 0x3f3f3f3f, sizeof(g));// 输入顶点数n和边数mcin >> n >> m;while (m--) { // 处理每一条边的输入int x, y, z;cin >> x >> y >> z;// 更新邻接矩阵g中的权值g[x][y] = min(g[x][y], z);}// 调用dijkstra函数求解dijkstra();return 0;
}

初始化邻接矩阵：
- memset(g, 0x3f3f3f3f, sizeof(g));：将邻接矩阵 g 初始化为一个很大的值（0x3f3f3f3f），表示初始时图中没有边。
输入图的边：
- cin >> n >> m;：读取顶点数 n 和边数 m。
- while (m--)：循环 m 次，读取每一条边的信息。
  - cin >> x >> y >> z;：读取边的起点 x、终点 y 和权重 z。
  - g[x][y] = min(g[x][y], z);：更新邻接矩阵 g 中的权值，如果有多条边连接同一对顶点，只保留权重最小的那条边。
调用Dijkstra算法：
- dijkstra();：调用 dijkstra 函数求解最短路径。
输出结果：
- dijkstra 函数会输出从起点到每个顶点的最短距离。

示例输入和输出

示例输入

示例输出

0 2 3 4 5

解释

顶点 1 到顶点 2 的最短距离为 2（1 -> 3 -> 2）。
顶点 1 到顶点 3 的最短距离为 3（1 -> 3）。
顶点 1 到顶点 4 的最短距离为 4（1 -> 3 -> 2 -> 4）。
顶点 1 到顶点 5 的最短距离为 5（1 -> 3 -> 2 -> 4 -> 5）。

关键点总结

邻接矩阵：使用二维数组 g[N][N] 表示图的结构，g[i][j] 表示从顶点 i 到顶点 j 的距离。
选择最短距离顶点：通过遍历所有顶点，找到未确定最短路径的顶点中距离最短的顶点。
更新邻接顶点的距离：通过当前顶点更新其邻接顶点的距离。
标记顶点：使用布尔数组 str 标记顶点是否已经确定了最短路径。

Dijkstra算法详细步骤解析

1. 初始化

在算法开始之前，需要进行以下初始化操作：

初始化距离数组 dis：
- 将 dis 数组中的所有元素初始化为一个很大的值（如 0x3f3f3f3f），表示从起点到其他顶点的距离初始为无穷大。
- 将起点的距离设置为 0，即 dis[start] = 0。
初始化访问标记数组 str：
- 将 str 数组中的所有元素初始化为 false，表示所有顶点初始时都未被访问过。
初始化邻接矩阵 g：
- 将邻接矩阵 g 中的所有元素初始化为一个很大的值（如 0x3f3f3f3f），表示初始时图中没有边。

2. 主循环

Dijkstra算法的核心是一个主循环，该循环执行 n 次（n 为顶点数），每次找到一个未访问的最短距离顶点，并更新其邻接顶点的距离。

选择未访问的最短距离顶点：
- 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u。
- 如果所有顶点都已被访问过，或者没有找到未访问的顶点，则退出循环。
更新邻接顶点的距离：
- 遍历顶点 u 的所有邻接顶点 v，如果通过 u 到达 v 的距离更短，则更新 dis[v]。
- 具体来说，如果 dis[u] + g[u][v] < dis[v]，则更新 dis[v] = dis[u] + g[u][v]。
标记顶点为已访问：
- 将顶点 u 标记为已访问，即 str[u] = true，避免重复处理。

3. 结果输出

在主循环结束后，dis 数组中存储了从起点到每个顶点的最短距离。遍历 dis 数组，输出结果：

如果 dis[i] 仍然是初始的大值（如 0x3f3f3f3f），表示没有路径到达顶点 i，输出 -1。
否则，输出 dis[i]，表示从起点到顶点 i 的最短距离。

示例执行过程

假设图的结构如下：

顶点数 n = 5
边数 m = 7
边的权重如下：
- 1 -> 2: 4
- 1 -> 3: 3
- 2 -> 4: 2
- 3 -> 2: 1
- 3 -> 4: 5
- 4 -> 5: 1
- 2 -> 5: 7

初始化

dis 数组：[0, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f]
str 数组：[false, false, false, false, false]

g 邻接矩阵：

[[0x3f3f3f3f, 4, 3, 0x3f3f3f3f, 0x3f3f3f3f],[0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 2, 0x3f3f3f3f],[0x3f3f3f3f, 1, 0x3f3f3f3f, 5, 0x3f3f3f3f],[0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 1],[0x3f3f3f3f, 7, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f]
]

第1次循环

选择未访问的最短距离顶点：
- 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 1（起点）。
更新邻接顶点的距离：
- 遍历顶点 1 的邻接顶点 2 和 3：
  - dis[2] = min(dis[2], dis[1] + g[1][2]) = min(0x3f3f3f3f, 0 + 4) = 4
  - dis[3] = min(dis[3], dis[1] + g[1][3]) = min(0x3f3f3f3f, 0 + 3) = 3
标记顶点为已访问：
- str[1] = true

第2次循环

选择未访问的最短距离顶点：
- 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 3（dis[3] = 3）。
更新邻接顶点的距离：
- 遍历顶点 3 的邻接顶点 2 和 4：
  - dis[2] = min(dis[2], dis[3] + g[3][2]) = min(4, 3 + 1) = 4
  - dis[4] = min(dis[4], dis[3] + g[3][4]) = min(0x3f3f3f3f, 3 + 5) = 8
标记顶点为已访问：
- str[3] = true

第3次循环

选择未访问的最短距离顶点：
- 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 2（dis[2] = 4）。
更新邻接顶点的距离：
- 遍历顶点 2 的邻接顶点 4 和 5：
  - dis[4] = min(dis[4], dis[2] + g[2][4]) = min(8, 4 + 2) = 6
  - dis[5] = min(dis[5], dis[2] + g[2][5]) = min(0x3f3f3f3f, 4 + 7) = 11
标记顶点为已访问：
- str[2] = true

第4次循环

选择未访问的最短距离顶点：
- 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 4（dis[4] = 6）。
更新邻接顶点的距离：
- 遍历顶点 4 的邻接顶点 5：
  - dis[5] = min(dis[5], dis[4] + g[4][5]) = min(11, 6 + 1) = 7
标记顶点为已访问：
- str[4] = true

第5次循环

选择未访问的最短距离顶点：
- 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 5（dis[5] = 7）。
更新邻接顶点的距离：
- 顶点 5 没有邻接顶点，无需更新。
标记顶点为已访问：
- str[5] = true

结果输出

遍历 dis 数组，输出从起点到每个顶点的最短距离：

dis[1] = 0
dis[2] = 4
dis[3] = 3
dis[4] = 6
dis[5] = 7

关键点总结

选择未访问的最短距离顶点：
- 每次选择未访问的顶点中距离最短的顶点，确保每一步都选择当前最优的顶点进行处理。
更新邻接顶点的距离：
- 通过当前顶点更新其邻接顶点的距离，确保每一步都更新到最新的最短距离。
标记顶点为已访问：
- 避免重复处理已访问的顶点，提高算法的效率。
结果输出：
- 最终输出从起点到每个顶点的最短距离，如果没有路径到达某个顶点，则输出 -1

Dijkstra算法解析

Dijkstra算法，用于求解图中从一个起点到其他所有节点的最短路径。解决单源最短路径问题的有效方法。条件有向带权路径时间复杂度 O（n平方） 方法步骤 1 把图上的点分为两个集合要求的起点和除了起点之外的点。能直达的写上权值不…...

编程日记 2025/5/14 23:42:49

本地部署DeepSeek教程（Mac版本）

第一步、下载 Ollama 官网地址：Ollama 点击 Download 下载我这里是 macOS 环境以 macOS 环境为主下载完成后是一个压缩包，双击解压之后移到应用程序： 打开后会提示你到命令行中运行一下命令，附上截图： 若遇…...

编程日记 2025/5/14 23:07:06

蓝桥杯算法笔记|差分学习

！前情回顾前缀和18437蓝桥账户中心练习代码： #include <iostream> using namespace std; int main() {// 请在此输入您的代码int n,q;cin>>n>>q;int a[n];for(int i0;i<n;i){cin>>a[i];}int sum[n];sum[0]a[0];for(int …...

编程日记 2025/5/12 14:50:24

一文速览DeepSeek-R1的本地部署——可联网、可实现本地知识库问答：包括671B满血版和各个蒸馏版的部署

前言自从deepseek R1发布之后「详见《一文速览DeepSeek R1：如何通过纯RL训练大模型的推理能力以比肩甚至超越OpenAI o1(含Kimi K1.5的解读)》」，deepseek便爆火爆火以后便应了“人红是非多”那句话，不但遭受各种大规模攻击，即便…...

编程日记 2025/5/14 22:45:09

【Redis】主从模式，哨兵，集群

主从复制单点问题： 在分布式系统中，如果某个服务器程序，只有一个节点（也就是一个物理服务器）来部署这个服务器程序的话，那么可能会出现以下问题： 1.可用性问题：如果这个机器挂了…...

编程日记 2025/5/14 7:47:49

成绩排序 #include<iostream> #include<algorithm> using namespace std; struct stu {string name;//名字int grade;//成绩 }; stu a[30]; bool cmp(stu l, stu r) {if (l.grade ! r.grade) return l.grade > r.grade;return l.name < r.name; } int main()…...

编程日记 2025/5/14 22:30:17

【通俗易懂说模型】线性回归（附深度学习、机器学习发展史）

🌈 个人主页：十二月的猫-CSDN博客 🔥 系列专栏： 🏀深度学习_十二月的猫的博客-CSDN博客 💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光目录 1. 前言 2. …...

编程日记 2025/5/14 22:55:12

Haproxy+keepalived高可用集群，haproxy宕机的解决方案

Haproxykeepalived高可用集群，允许keepalived宕机，允许后端真实服务器宕机，但是不允许haproxy宕机， 所以下面就是解决方案 keepalived配置高可用检测脚本 ，master和backup都要添加配置脚本 # vim /etc/keepalived…...

编程日记 2025/5/14 23:03:41

python学opencv|读取图像（五十六）使用cv2.GaussianBlur()函数实现图像像素高斯滤波处理

【1】引言前序学习了均值滤波和中值滤波，对图像的滤波处理有了基础认知，相关文章链接为： python学opencv|读取图像（五十四）使用cv2.blur()函数实现图像像素均值处理-CSDN博客 python学opencv|读取图像（…...

编程日记 2025/5/14 22:38:07

电梯系统的UML文档13

5.2.6 CarPositionControl 的状态图图 24: CarPositionControl 的状态图 5.2.7 Dispatcher 的状态图图 25: Dispatcher 的状态图 5.3 填补从需求到状态图鸿沟的实用方法状态图能对类的行为，一个用例，或系统整体建模。在本文中，状态图…...

编程日记 2025/5/12 21:01:24

CSDN原力值提升秘籍：解锁社区活跃新姿势

在 CSDN 这个技术交流的大舞台上，原力值不仅是个人活跃度的象征，更是开启更多权益与福利的钥匙。最近，我出于自身需求，一头扎进了提升原力值的研究中，经过多方探索与资料整理，现在就迫不及待地把这些干货分…...

编程日记 2025/5/14 23:25:08

互联网行业常用12个数据分析指标和八大模型

本文目录前言一、互联网线上业务数据分析的12个指标 1. 用户数据（4个） (1) 存量（DAU/MAU） (2) 新增用户 (3) 健康程度（留存率） (4) 渠道来源 2. 用户行为数据（4个） (1) 次数/频率…...

编程日记 2025/5/14 23:34:45

gltf工具

gltf 在线工具 ONLINE 3D VIEWER 3dviewer.netgltf-viewer cos.3dzhanting.cnviewer www.niushifu.topglTF Viewer gltf-viewer.donmccurdy.comGLTF 在线编辑器 gltf.nsdt.cloudgltfeditor...

编程日记 2025/5/14 12:25:44

车载软件架构 --- 基于AUTOSAR软件架构的ECU开发流程小白篇

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 简单，单纯，喜欢独处，独来独往，不易合同频过着接地气的生活…...

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

Vue.js 如何选择合适的组件库

Vue.js 如何选择合适的组件库大家在开发 Vue.js 项目的时候，都会面临一个问题：我该选择哪个组件库？ 市面上有很多优秀的 Vue 组件库，比如 Element Plus、Vuetify、Quasar 等，它们各有特点。选择合适的组件库&#xf…...

编程日记 2025/5/14 22:31:20

JavaScript系列（58）--性能监控系统详解

JavaScript性能监控系统详解 📊 今天，让我们深入探讨JavaScript的性能监控系统。性能监控对于保证应用的稳定性和用户体验至关重要。性能监控基础概念 🌟 💡 小知识：JavaScript性能监控是指通过收集和分析各种性能指…...

编程日记 2025/5/14 23:15:22

Flutter 与 React 前端框架对比：深入分析与实战示例

Flutter 与 React 前端框架对比：深入分析与实战示例在现代前端开发中，Flutter 和 React 是两个非常流行的框架。Flutter 是 Google 推出的跨平台开发框架，支持从一个代码库生成 iOS、Android、Web 和桌面应用；React 则是 Facebo…...

编程日记 2025/5/13 1:01:57

AI-on-the-edge-device - 将“旧”设备接入智能世界

人工智能无处不在，从语音到图像识别。虽然大多数 AI 系统都依赖于强大的处理器或云计算，但**边缘计算**通过利用现代处理器的功能，使 AI 更接近最终用户。本项目演示了使用 **ESP32**（一种低成本、支持 AI 的设备）进行…...

编程日记 2025/5/14 23:39:35

站在JavaScript的视角去看，HTML的DOM和GLTF的Json数据。

很多前端小伙伴没有见过、操作过gltf文件，对非常懵逼，本文从前端小伙伴最熟悉的dom模型为切入口，以类别的方式来学习一下gltf文件。一、结构与组织形式 HTML DOM（文档对象模型）： 树形结构：HT…...

编程日记 2025/5/12 17:55:33

js --- 获取时间戳

介绍使用js获取当前时间戳语法 Date.now()...

编程日记 2025/5/14 22:15:37

冰蝎v3.0 beta7来啦

我用了一台kali，一台centos，一台windows，做了一个文件上传和一个反弹shell实验，载荷是AES加密的，终于感受到了对加密流量的无可奈何~ kali（php8.1）centos（php7.1）window…...

编程日记 2025/5/14 23:01:30

将markdown文件和LaTex公式转为word

通义千问等大模型生成的回答多数是markdown类型的，需要将他们转为Word文件一 pypandoc 介绍 1. 项目介绍 pypandoc 是一个用于 pandoc 的轻量级 Python 包装器。pandoc 是一个通用的文档转换工具，支持多种格式的文档转换，如 Markdown、HTM…...

编程日记 2025/5/6 1:21:12

Elasticsearch Kibana的下载与安装

1.下载Elasticsearch安装包 Elastic — 搜索 AI 公司 | Elastic Download Elasticsearch | Elastic 2.下载Kibana安装包 Download Kibana Free | Get Started Now | Elastic http://localhost:5601/?code708785...

编程日记 2025/5/14 22:06:31

WPS计算机二级•幻灯片的配色、美化与动画

听说这是目录哦配色基础颜色语言❤️使用配色方案🩷更改PPT的颜色🧡PPT动画添加的原则💛PPT绘图工具💚自定义设置动画💙使用动画刷复制动画效果🩵制作文字打字机效果💜能量站😚 配色…...

编程日记 2025/5/12 19:10:02

高精度乘法（高×高）

高精度乘法（高高） 前言 ACWing算法基础课讲解了高低的乘法，这里高高作为一个进一步的补充，也是对闫总的板子做一个补充。以下内容改编自《洛谷深入浅出》123页，我对代码进行了一点修改。 A*B Problem P1303 题目…...

编程日记 2025/5/14 2:31:21

出现 Can not find ‘Converter‘ support class Year 解决方法

目录前言1. 问题所示2. 原理分析3. 解决方法前言 🤟 找工作，来万码优才：👉 #小程序://万码优才/r6rqmzDaXpYkJZF 1. 问题所示执行代码的时候，出现如下问题： 2025-02-03 19:16:23.638 |...

编程日记 2025/5/8 4:20:51

一表总结 Java 的3种设计模式与6大设计原则

设计模式通常分为三大类：创建型、结构型和行为型。创建型模式：主要用于解决对象创建问题结构型模式：主要用于解决对象组合问题行为型模式：主要用于解决对象之间的交互问题创建型模式创建型模式关注于对象的创建机制&#xf…...

编程日记 2025/5/8 13:45:14

蓝桥与力扣刷题（141 环形链表）

题目：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的…...

编程日记 2025/5/12 20:00:13

Cursor如何使用Google Gemini以及碰到的坑

Cursor如何使用Google Gemini以及碰到的坑 Cursor介绍下载安装Google Gemini介绍Google Gemini 官网申请Google Gemini API网址配置Cursor使用Google Gemini打开Corsur设置 Cursor介绍 ‌Cursor是一款基于人工智能的代码编辑器，旨在帮助开发者更高效地编写代码。‌…...

编程日记 2025/5/12 20:01:27

e2studio开发RA4M2(6)----GPIO外部中断（IRQ）配置

e2studio开发RA4M2.6--GPIO外部中断（IRQ）配置概述视频教学样品申请硬件准备参考程序源码下载新建工程工程模板保存工程路径芯片配置工程模板选择时钟设置SWD调试口设置GPIO口配置按键中断配置中断回调函数主程序概述 GPIO（通用输入/输出&a…...

编程日记 2025/5/11 18:23:25

day38|leetcode 322零钱兑换，279.完全平方数，139.单词拆分

322. 零钱兑换给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是…...

编程日记 2025/5/12 13:26:20

Windsurf cursor vscode+cline 与Python快速开发指南

Windsurf简介 Windsurf是由Codeium推出的全球首个基于AI Flow范式的智能IDE，它通过强大的AI助手功能，显著提升开发效率。Windsurf集成了先进的代码补全、智能重构、代码生成等功能，特别适合Python开发者使用。 Python环境配置 1. Conda安装…...

编程日记 2025/5/11 14:55:10

使用shell命令安装virtualbox的虚拟机并导出到vagrant的Box

0. 安装virtualbox and vagrant [rootolx79vagrant ~]# cat /etc/resolv.conf #search 114.114.114.114 nameserver 180.76.76.76-- install VirtualBox yum install oraclelinux-developer-release-* wget https://yum.oracle.com/RPM-GPG-KEY-oracle-ol7 -O /etc/pki/rpm-g…...

编程日记 2025/5/12 5:38:33

代码解析

全局变量定义

Dijkstra算法实现

主函数

示例输入和输出

示例输入

示例输出

解释

关键点总结

Dijkstra算法详细步骤解析

1. 初始化

2. 主循环

3. 结果输出

示例执行过程

初始化

第1次循环

第2次循环

第3次循环

第4次循环

第5次循环

结果输出

关键点总结

相关文章：