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

C++基础算法9：Dijkstra

news 来源：原创 2025/8/25 16:20:27

1、概念

Dijkstra算法 是一种用于计算图中单源最短路径的算法，主要用于加权图（图中边的权重可以不同）中找出从起点到各个其他节点的最短路径。

Dijkstra算法的核心概念：

图的表示：

  • 有向图：图的边是有方向的，表示从一个节点到另一个节点的路径。
  • 加权图：图的每条边都有一个权重，表示通过该边的代价或距离。

最短路径：

  • 计算从一个起点（源节点）到所有其他节点的最短路径，最短路径的定义是路径的权重之和最小。

贪心策略：

  • Dijkstra算法是一种贪心算法，即每次选择当前最短的路径扩展，不一定考虑全局的最优解，但局部选择最优后，最终能得到全局最优。

2、实战例子

给定n个点，m条边，求最后一个点的最短路径。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int N = 1e5 + 10;
int w[N], e[N], ne[N], h[N]; // 边的权重、目标节点、邻接链表、每个节点的头指针
int dist[N], state[N]; // dist存储最短距离，state表示节点是否已处理
int idx = 0; // 当前边的索引
int n, m; // n为节点数，m为边数// 邻接表
void add(int a, int b, int c)
{e[idx] = b;     // 边的目标节点ne[idx] = h[a]; // 当前边指向的上一个节点的邻接边w[idx] = c;     // 边的权重h[a] = idx++;   // 更新节点a的邻接链表头为当前边的索引
}// Dijkstra算法的实现
void dijkstra()
{memset(dist, 0x3f3f3f3f, sizeof(dist)); // 初始化dist为无穷大dist[1] = 0; // 起点到自身的距离为0for (int i = 0; i < n; i++) {int t = -1;for (int j = 1; j <= n; j++) { // 找出未访问的距离最小的节点if(state[j] == 0 && (t == -1 || dist[j] < dist[t]))t = j;}state[t] = 1; // 标记节点t为已访问for (int k = h[t]; k != -1; k = ne[k]) { // 遍历t的所有邻接边int x = e[k]; // x是t的一个邻接节点dist[x] = min(dist[x], dist[t] + w[k]); // 更新dist[x]为更小的值}}
}int main()
{memset(h, -1, sizeof(h)); // 初始化所有节点的邻接链表头为-1cin >> n >> m; // 输入节点数n和边数mwhile (m--) {int x, y, z;cin >> x >> y >> z; // 输入每条边add(x, y, z); // 添加边}dijkstra(); // 运行Dijkstra算法if (dist[n] != 0x3f3f3f3f) // 如果到达节点n的最短距离不是无穷大，输出最短路径cout << dist[n];elsecout << -1; // 否则输出-1，表示无法到达节点nreturn 0;
}

3、难点

邻接表

每一个节点可能指向多个其他节点，构建的邻接表核心还是单链表的扩展。

每一个节点初始都节点都指向-1，当该节点需要指向新的节点时，头节点表示该节点的索引值。因此，每一个节点都可以看作是一条包含头节点的单链表。在求解每个节点的最短路径时，就需要利用链表的特性把每个链表中的数据都循环到。

相关文章：

C++基础算法9：Dijkstra

1、概念 Dijkstra算法 是一种用于计算图中单源最短路径的算法&#xff0c;主要用于加权图&#xff08;图中边的权重可以不同&#xff09;中找出从起点到各个其他节点的最短路径。 Dijkstra算法的核心概念&#xff1a; 图的表示&#xff1a; 有向图&#xff1a;图的边是有方…...

编程日记 2025/8/25 16:20:27

5块钱的无忧套餐卡可以变成流量卡吗

电信的 5 块钱无忧套餐卡理论上可以变成流量卡&#xff0c;但会受到一些条件限制&#xff0c;以下是具体介绍&#xff1a; 中国电信无忧卡简介 中国电信无忧卡是电信推出的低月租套餐&#xff0c;月租仅 5 元&#xff0c;包含 200M 国内流量、来电显示和 189 邮箱&#xff0c;全…...

编程日记 2025/8/22 2:11:39

word页眉去掉线

直接双击页眉处于下面状态&#xff1a; 然后&#xff1a; 按CtrlshiftN即可&#xff01;去除...

编程日记 2025/8/25 16:13:06

Spark，Idea中编写Spark程序 2

Idea中编写Spark程序 一、修改pom.xml文件 <build><sourceDirectory>src/main/scala</sourceDirectory><testSourceDirectory>src/test/scala</testSourceDirectory> <!-- 添加必要的插件以打包scala程序--><plugins><plu…...

编程日记 2025/8/25 16:13:06

GTID（全局事务标识符）的深入解析

GTID（全局事务标识符）的深入解析 GTID（Global Transaction Identifier）是 MySQL 5.6 版本引入的一项核心功能，旨在解决传统主从复制中的痛点。它通过为每个事务赋予一个全局唯一的标识符，彻底改变了复制的管理方式。 一、传统复制的痛点 在 GTID 出现之前，MySQL 主从…...

编程日记 2025/8/25 16:13:05

Circular Plot系列(一): 环形热图绘制

针对近期多个粉丝咨询环形图的绘制&#xff0c;我意识到&#xff0c;我们似乎没有真正介绍过circle图&#xff0c;但这一类图确是非常常用的图&#xff0c;所以这里详细学习一下circle的绘制&#xff0c;使用的是circlize包&#xff0c;功能很完善&#xff1a;安装包, #https:/…...

编程日记 2025/8/25 16:17:52

字符串匹配 之 KMP算法

文章目录 习题28.找出字符串中第一个匹配项的下标1392.最长快乐前缀 本博客充分参考灵神和知乎的另一位博主 灵神KMP算法模版 知乎博主通俗易懂讲解 对于给定一个主串S和一个模式串P,如果让你求解出模式串P在主串S中匹配的情况下的所有的开始下标简单的做法又称为Brute-Force算…...

编程日记 2025/8/25 8:00:26

「一针见血能力」的终极训练手册

缘起 和顶尖的高手接触以后&#xff0c;发现他们在表达沟通上面的能力真的太强了&#xff0c;仿佛有种一阵见血看问题的能力&#xff0c;这种拨开浓雾看本质的能力是嘈杂世界防止上当受骗的不二法门. 网上找了一些训练方法&#xff0c;可以试试训练锐化思维&#xff0c;提高表…...

编程日记 2025/8/25 16:14:22

Linux 入门：操作系统进程详解

目录 一.冯诺依曼体系结构 一&#xff09;. 软件运行前为什么要先加载&#xff1f;程序运行之前在哪里&#xff1f; 二&#xff09;.理解数据流动 二.操作系统OS(Operator System) 一&#xff09;.概念 二&#xff09;.设计OS的目的 三&#xff09;.如何理解操作系统…...

编程日记 2025/8/25 16:15:45

【2025软考高级架构师】——2024年05月份真题与解析

摘要 本文内容是关于2025年软考高级架构师考试的相关资料&#xff0c;包含2024年05月份真题与解析。其中涉及体系结构演化的步骤、OSI协议中能提供安全服务的层次、数据库设计阶段中进行关系反规范化的环节等知识点&#xff0c;还提及了软考高级架构师考试的多个模块&#xff…...

编程日记 2025/8/25 16:17:25

Mybatis执行流程知多少

思维导图&#xff1a; 一、MyBatis 执行流程概述 MyBatis 的执行流程可以大致分为以下几个关键步骤&#xff1a;配置加载、会话创建、SQL 执行和结果处理。下面我们将逐步详细介绍每个步骤。 二、配置加载 1. 配置文件的重要性 MyBatis 的配置文件是整个框架的基础&#xff0c;…...

编程日记 2025/8/25 16:12:02

码蹄集——偶数位、四边形坐标

目录 MT1039 偶数位 MT1051 四边形坐标 MT1039 偶数位 思路&#xff1a;直接使用按位操作符 一个整型数字是32位,十六进制表示为0x后跟8个字符,每个字符为0-e,代表0-15; 把偶数位改为0,就是用0去&偶数位,用1去&奇数位,即0xAAAAAAAA,A代表10,1010(从右往 左依次为0位,…...

编程日记 2025/8/25 16:16:15

Java 中使用 Callable 创建线程的方法

一、Callable 接口概述​ Callable接口位于java.util.concurrent包中&#xff0c;与Runnable接口类似&#xff0c;同样用于定义线程执行的任务&#xff0c;但它具有以下独特特性&#xff1a;​ 支持返回值&#xff1a;Callable接口声明了一个call()方法&#xff0c;该方法会在…...

编程日记 2025/8/25 13:18:55

代码随想录算法训练营Day44

力扣1045.不相交的线【medium】 力扣53.最大子数组和【medium】 力扣392.判断子序列【easy】 一、力扣1045.不相交的线【medium】 题目链接&#xff1a;力扣1045.不相交的线 视频链接&#xff1a;代码随想录 题解链接&#xff1a;灵茶山艾府 1、思路 和1143.最长公共子序列一…...

编程日记 2025/8/25 16:14:31

Java大师成长计划之第12天：性能调优与GC原理

&#x1f4e2; 友情提示&#xff1a; 本文由银河易创AI&#xff08;https://ai.eaigx.com&#xff09;平台gpt-4o-mini模型辅助创作完成&#xff0c;旨在提供灵感参考与技术分享&#xff0c;文中关键数据、代码与结论建议通过官方渠道验证。 在 Java 编程中&#xff0c;性能调优…...

编程日记 2025/8/25 16:14:32

【MySQL】索引（重要）

目录 一、索引本质&#xff1a; 索引的核心作用 索引的优缺点 二、预备知识&#xff1a; 硬件理解&#xff1a; 软件理解&#xff1a; MySQL与磁盘交互基本单位&#xff1a; 三、索引的理解&#xff1a; 理解page&#xff1a; 单个page&#xff1a; 多个page&#x…...

编程日记 2025/8/25 16:15:44

C++多态（上）

目录 一、多态的概念 二、多态的定义及实现 1. 多态的构成条件 2. 虚函数 3. 虚函数的重写 4. C11 override 和 final 4.1 final 关键字 4.2 override 关键字 5. 重载、覆盖&#xff08;重写&#xff09;、隐藏&#xff08;重定义&#xff09;的对比 三、抽象类 1. 概…...

编程日记 2025/8/25 16:17:26

【AI提示词】 复利效应教育专家

提示说明 一位拥有金融学和教育学背景的知识型内容创作者&#xff0c;擅长用简单易懂的语言向读者解释复杂概念 提示词 # Role: 复利效应教育专家## Profile - language: 中文 - description: 一位拥有金融学和教育学背景的知识型内容创作者&#xff0c;擅长用简单易懂的语言…...

编程日记 2025/8/25 16:13:05

嵌入式系统基础知识

目录 一、冯诺依曼结构与哈佛结构 &#xff08;一&#xff09;冯诺依曼结构 &#xff08;二&#xff09;哈佛架构 二、ARM存储模式 &#xff08;一&#xff09;大端模式 &#xff08;二&#xff09;小端模式 &#xff08;三&#xff09;混合模式 三、CISC 与 RISC &am…...

编程日记 2025/8/25 0:45:20

如何克服情绪拖延症？

引言 你是否也曾有过这样的经历&#xff1f; 明明手头有重要的工作&#xff0c;却总是忍不住刷手机、看视频&#xff0c;直到最后一刻才匆忙赶工&#xff1f; 你是否在心里暗暗发誓“明天一定好好干”&#xff0c;但第二天依旧重复着同样的拖延&#xff1f; 其实&#xff0…...

编程日记 2025/8/25 16:14:23

【操作系统】哲学家进餐问题

问题描述 哲学家进餐问题是并发编程中的一个经典问题&#xff0c;描述了五位哲学家围坐在一张圆桌旁&#xff0c;他们的生活由思考和进餐组成。在圆桌上有五个盘子&#xff0c;每位哲学家面前一个盘子&#xff0c;盘子之间有一支叉子。哲学家进餐需要同时使用左右两支叉子。问题…...

编程日记 2025/8/25 16:14:32

Kotlin协程解析

目录 一、协程的使用 二、协程的执行原理 2.1、挂起函数的反编译代码及执行分析 2.2、协程执行流程分析 2.2.1、createCoroutineUnintercepted方法 2.2.2、intercepted方法 2.2.3、resumeCancellableWith方法 2.3、Dispatcher----分发器的实现 2.3.1、Main 分发器的实…...

编程日记 2025/8/25 16:11:59

Nginx核心功能 02

目录 Nginx代理技术核心概念 &#xff08;一&#xff09;正向代理&#xff08;Forward Proxy&#xff09; 1. 基本定义 2. 技术原理 3. 应用场景 &#xff08;二&#xff09;反向代理&#xff08;Reverse Proxy&#xff09; 1. 基本定义 2. 技术原理 3. 应用场景 一、…...

编程日记 2025/8/25 16:18:47

聊聊对Mysql的理解

目录 1、Sql介绍 1.1、SQL的分类 1.2、数据库的三大范式 1.3、数据表的约束 1.4、约束的添加与删除 2、核心特性 3、主要组件 4、数据结构原理 5、索引失效 6、常用问题 7、优势与局限 前言 MySQL是一个开源的关系型数据库管理系统(RDBMS)&#xff0c;由瑞典MySQL A…...

编程日记 2025/8/25 16:16:14

「Mac畅玩AIGC与多模态17」开发篇13 - 条件判断与分支跳转工作流示例

一、概述 本篇在多节点串联的基础上，进一步引入条件判断与分支跳转机制，实现根据用户输入内容动态走不同执行路径。开发人员将学习如何配置判断节点、定义分支规则，以及如何在工作流中引导执行方向，完成基础的逻辑控制。 二、环境准备 macOS 系统Dify 平台已部署并可访问…...

编程日记 2025/8/25 1:43:50

pycharm terminal 窗口打不开了

参考添加链接描述powershell.exe改为cmd.exe发现有一个小正方形&#xff0c;最大化可以看见了。...

编程日记 2025/8/25 16:12:02

JAVA：使用 MapStruct 实现高效对象映射的技术指南

1、简述 在 Java 开发中，对象之间的转换是一个常见的需求，尤其是在 DTO（数据传输对象）和实体类之间的转换过程中。手动编写转换代码既耗时又容易出错，而 MapStruct 是一个优秀的对象映射框架，可以通过注解生成高效的对象转换代码，从而大大提升开发效率。 本文将介绍 M…...

编程日记 2025/8/23 6:01:35

Linux线程深度解析：从基础到实践

Linux线程深度解析&#xff1a;从基础到实践 一、线程基础概念 1. 进程与线程定义 进程&#xff1a;一个正在运行的程序&#xff0c;是操作系统资源分配的最小单位&#xff08;拥有独立的地址空间、文件描述符等资源&#xff09;&#xff0c;状态包括就绪、运行、阻塞。线程…...

编程日记 2025/8/22 4:29:21

【ROS2】launch启动文件如何集成到ROS2（Python版本）

一、简单实操 1.创建/打开一个功能包 mkdir -p my_ws/src cd my_ws/src ros2 pkg create my_pkg_example --build-type ament_python 2.创建Launch文件的存放目录 将所有启动文件都存储在launch包内的目录中。 目录结构如下所示&#xff1a; src/my_pkg_example/launch/…...

编程日记 2025/8/24 8:28:11

用 PyTorch 轻松实现 MNIST 手写数字识别

用 PyTorch 轻松实现 MNIST 手写数字识别 引言 在深度学习领域&#xff0c;MNIST 数据集就像是 “Hello World” 级别的经典入门项目。它包含大量手写数字图像及对应标签&#xff0c;非常适合新手学习如何搭建和训练神经网络模型。本文将基于 PyTorch 框架&#xff0c;详细拆…...

编程日记 2025/8/21 7:21:49

碰撞检测学习笔记

目录 SUMO 模拟碰撞 LimSim pygame模拟碰撞检测 SUMO 模拟碰撞 LimSim 多模态大语言模型&#xff08;M&#xff09;LLM的出现为人工智能开辟了新的途径&#xff0c;特别是提供增强的理解和推理能力&#xff0c;为自动驾驶开辟了新途径。本文介绍LimSim&#xff0c;LimSim的…...

编程日记 2025/8/22 4:29:14

Sway初体验

Sway&#xff08;缩写自 SirCmpwn’s Wayland compositor[1]&#xff09;是一款专为 Wayland 设计的合成器&#xff0c;旨在与 i3 完全兼容。根据官网所述&#xff1a; Sway 是 Wayland 的合成器&#xff0c;也是 x11 的 i3 窗口管理器的替代品。它可以根据您现有的 i3 配置工作…...

编程日记 2025/8/22 4:29:11

《工业社会的诞生》章节

工业革命的技术前奏 早期工业技术双引擎&#xff1a; 【火药武器】&#xff1a;重塑战争形态与经济地理 新式青铜炮助力殖民扩张&#xff0c;开辟全球贸易网络 高桅帆船&#xff08;西班牙大帆船&#xff09;实现洲际航行 战争规模化倒逼中央集权&#xff0c;催生国家-商人…...

编程日记 2025/8/22 4:29:09

消息队列MQ

参考资料&#xff1a;https://cloud.tencent.com/developer/article/2335397 https://www.cnblogs.com/hahaha111122222/p/18457859 消息队列是大型分布式系统不可缺少的中间件&#xff0c;也是高并发系统的基石中间件 消息队列 消息队列 Message Queue 消息队列是利用高效可…...

编程日记 2025/8/22 4:29:06

LangChain4J-XiaozhiAI 项目分析报告

LangChain4J-XiaozhiAI 项目分析报告 GitHub 链接 1. 项目概述 本项目名为 “硅谷小智&#xff08;医疗版&#xff09;”&#xff0c;是一个基于 Java 技术栈和 LangChain4J 框架构建的 AI 聊天助手应用。其核心目标是利用大型语言模型&#xff08;LLM&#xff09;的能力&am…...

编程日记 2025/8/24 12:44:27

学习spring boot-拦截器Interceptor，过滤器Filter

目录 拦截器Interceptor 过滤器Filter 关于过滤器的前置知识可以参考&#xff1a; 过滤器在springboot项目的应用 一&#xff0c;使用WebfilterServletComponentScan 注解 1 创建过滤器类实现Filter接口 2 在启动类中添加 ServletComponentScan 注解 二&#xff0c;创建…...

编程日记 2025/8/24 1:42:59

【程序+论文】大规模新能源并网下的火电机组深度调峰经济调度

目录 1 主要内容 讲解重点 2 讲解视频及代码 1 主要内容 该视频为《大规模新能源并网下的火电机组深度调峰经济调度》代码讲解内容&#xff0c;该程序有完全对照的论文&#xff0c;以改进IEEE30节点作为研究对象&#xff0c;系统包括5个火电机组和2个新能源机组&#xff0c;…...

编程日记 2025/8/22 4:28:58

【win11 】win11 键盘测试

我的键盘是支持mac和win的&#xff0c;fn tab 就能切换&#xff0c;有可能是用错了模式&#xff0c;导致 我alt a 就会弹出 win11的 wifi 等菜单控制 键盘测试网站 https://keyboard.bmcx.com/ 识别到我按下的是alt...

编程日记 2025/8/21 15:26:05

再识动静态库

动静态库 1 手动制作静态库2 手动调用静态库方式一&#xff1a;&#xff08;安装到系统&#xff09;方式二&#xff1a;&#xff08;和源文件一起&#xff09;方式三&#xff1a;&#xff08;使用带路径的库&#xff09; 3 动态库制作与使用方式一&#xff1a;拷贝到系统方式二…...

编程日记 2025/8/22 4:28:51

前端 uni-app 初步使用指南

在数字化浪潮下&#xff0c;实现应用多端适配成为开发者的刚需。uni-app 凭借 “一次编写&#xff0c;多端运行” 的特性&#xff0c;极大提升了开发效率&#xff0c;成为前端开发的热门选择。如果你是首次接触 uni-app&#xff0c;这篇文章将带你开启 uni-app 的使用之旅&…...

编程日记 2025/8/22 4:28:48

尼卡音乐 1.1.1 | 免费畅听全网音乐，支持无损下载，无广告无需注册登录

尼卡音乐是一款可以免费畅听全网音乐的应用程序&#xff0c;支持免费下载无损高品质音源&#xff0c;并且没有任何广告&#xff0c;无需注册登录。用户可以轻松搜索全网无损音质音源&#xff0c;并可将其他音乐APP的歌单导入&#xff0c;让音乐陪你开心一整天。该应用彻底拒绝臃…...

编程日记 2025/8/22 4:28:45

33.降速提高EMC能力

降速提高EMC能力 1. 电磁兼容问题的错误累积效应2. 降速减少累积效应的机理分析 1. 电磁兼容问题的错误累积效应 2. 降速减少累积效应的机理分析 降速之后&#xff0c;信号的波形更完整&#xff0c;容错空间更大&#xff1b;另外边沿变缓&#xff0c;对外干扰也会减小。...

编程日记 2025/8/22 4:28:43

【赵渝强老师】TiDB的MVCC机制

TiDB是一款开源的国产分布式关系型数据库。TiKV是TiDB的行存引擎&#xff0c;它支持多版本并发控制(Multi-Version Concurrency Control,MVCC)。假设有这样一种场景&#xff1a;某客户端A在写一个Key&#xff0c;另一个客户端B同时在对这个Key进行读操作。如果没有数据的多版本…...

编程日记 2025/8/21 21:02:29

数电填空题整理（适用期末考试）

在下列门电路中&#xff0c;OC门能实现“线与”逻辑功能&#xff1b; 三态门能用于总线结构的数 据传输&#xff1b;传输门 能实现模拟信号的双向传输。 并联比较型A/D转换器的转换速度最快&#xff0c; 双积分型A/D转换器的稳定性和抗干扰能力最好 TTL与非门多余的输入端应该…...

编程日记 2025/8/25 12:17:18

node核心学习

目录 1-1node概述 1-2全局对象 1-3Node的模块化细节 1-4Node中的ES模块化 1-5基本内置模块 OS模块&#xff1a; path模块&#xff1a; url模块&#xff1a; util模块&#xff1a; 1-6文件IO I/O&#xff1a;input output fs模块的方法 代码示例&#xff1a; 练习…...

编程日记 2025/8/22 4:28:37

基于 PyQt 的YOLO目标检测可视化界面+ nuitka 打包

在人工智能和计算机视觉领域&#xff0c;YOLO&#xff08;You Only Look Once&#xff09;是一种广泛使用的实时目标检测算法。为了直观地展示YOLO算法的检测效果&#xff0c;我们使用Pyqt框架进行检测结果的可视化&#xff0c;同时为了使其能够脱离Python环境&#xff0c;我们…...

编程日记 2025/8/25 14:50:10

234树和红黑树

首先&#xff0c;把目光聚集在234树中 以下是234的三种节点&#xff08;可以有更多这里使用以下的三个&#xff09;&#xff1a; 右侧是节点转换成红黑树节点的样子。 接下来会用以下序列进行1234树的搭建和红黑树的搭建&#xff1a; 首先是234树 2-3-4树&#xff08;234树&…...

编程日记 2025/8/22 4:28:33

GenCLS++：通过联合优化SFT和RL，提升生成式大模型的分类效果

摘要&#xff1a;作为机器学习中的一个基础任务&#xff0c;文本分类在许多领域都发挥着至关重要的作用。随着大型语言模型&#xff08;LLMs&#xff09;的快速扩展&#xff0c;特别是通过强化学习&#xff08;RL&#xff09;的推动&#xff0c;对于更强大的分类器的需求也在不…...

编程日记 2025/8/22 4:28:31

maven坐标导入jar包时剔除不需要的内容

maven坐标导入jar包时剔除不需要的内容 问题描述解决方案 问题描述 maven坐标导入jar包时剔除不需要的内容 解决方案 Spring Boot 默认使用 Logback&#xff0c;需在 pom.xml 中排除其依赖&#xff1a; <dependency><groupId>org.springframework.boot</gro…...

编程日记 2025/8/22 4:28:29

Oracle OCP认证考试考点详解083系列06

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 26. 第26题&#xff1a; 题目 解析及答案&#xff1a; 关于块介质恢复&#xff0c;以下哪三项是正确的&#xff1f; A) 需恢复一个或多个…...

编程日记 2025/8/22 4:28:27