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

Dijkstra 算法 是什么?

Dijkstra 算法

Dijkstra 算法是一种经典的最短路径算法,用于在图(有向或无向图)中找到从起点到其他所有节点的最短路径。它以广度优先搜索的方式,逐步扩展到目标节点,确保计算出的路径是最短的。


1. Dijkstra 算法的基本概念

特点
  • 适用于非负权值的图。
  • 能够找到从单一源节点到所有其他节点的最短路径。
输入
  • 一个图(节点和边)。
  • 起始节点(源节点)。
输出
  • 从起始节点到其他所有节点的最短路径长度。
  • 如果需要,可以记录路径上的具体节点。

2. 核心思想

Dijkstra 算法的核心思想是:

  • 利用贪心策略,每次选择当前未访问的、距离起点最近的节点进行扩展。
  • 一旦访问一个节点,其最短路径就不会被更新(路径确定性)。

3. 算法步骤

初始化
  1. 创建一个距离表(distance table):
    • 对每个节点初始化为无穷大(∞),表示当前未知最短路径。
    • 起点的距离设为 0:distance[start] = 0
  2. 创建一个访问表(visited set),记录已访问的节点。
  3. 使用一个优先队列小顶堆(priority queue)存储待访问节点及其距离。
主循环
  1. 从优先队列中取出距离起点最近的未访问节点 ( u )。
  2. 对 ( u ) 的每个邻居节点 ( v ):
    • 计算从起点通过 ( u ) 到 ( v ) 的路径距离:distance[v] = min(distance[v], distance[u] + weight(u, v))
    • 如果路径距离更新了,将 ( v ) 加入优先队列。
  3. 将 ( u ) 标记为已访问。
  4. 重复上述步骤,直到优先队列为空或所有节点的最短路径确定。
路径恢复

如果需要输出路径,可以在更新距离表时记录每个节点的前驱节点,最后从目标节点回溯到起点。


4. 伪代码

Dijkstra(Graph, Start):# 初始化distance = {node: ∞ for node in Graph}distance[Start] = 0visited = set()priority_queue = [(0, Start)]  # (distance, node)while priority_queue:# 取出当前距离最小的节点current_distance, current_node = priority_queue.pop()if current_node in visited:continuevisited.add(current_node)# 更新邻居节点的距离for neighbor, weight in Graph[current_node]:new_distance = current_distance + weightif new_distance < distance[neighbor]:distance[neighbor] = new_distancepriority_queue.append((new_distance, neighbor))return distance

5. 示例

图示

假设一个加权图如下:

   (A)--1--(B)--4--(D)|       |2       2|       |(C)--1--(E)
输入
  • 起点:A
  • 图的权值:Graph = {A: [(B, 1), (C, 2)], B: [(A, 1), (D, 4), (E, 2)], C: [(A, 2), (E, 1)], ...}
执行步骤
  1. 初始化:distance = {A: 0, B: ∞, C: ∞, D: ∞, E: ∞}
  2. 选择 ( A ) 开始,更新邻居:
    • ( distance[B] = 0 + 1 = 1 )
    • ( distance[C] = 0 + 2 = 2 )
  3. 选择 ( B ):
    • ( distance[D] = 1 + 4 = 5 )
    • ( distance[E] = 1 + 2 = 3 )
  4. 选择 ( C ):
    • ( distance[E] = min(3, 2 + 1) = 3 )
  5. 选择 ( E )、( D ),最终得到:
    • distance = {A: 0, B: 1, C: 2, D: 5, E: 3}
输出

从 ( A ) 到各节点的最短路径距离:

  • ( A \to B: 1 )
  • ( A \to C: 2 )
  • ( A \to D: 5 )
  • ( A \to E: 3 )

6. 优缺点

优点
  • 高效:适用于稠密图,时间复杂度为 ( O((V + E) \log V) )(使用堆实现)。
  • 稳定:保证找到从起点到各节点的最短路径。
缺点
  • 限制:不能处理带负权边的图。
  • 局限性:只能从一个起点出发计算最短路径,无法同时处理多源问题。

7. 应用场景

  1. 导航系统:计算最短路径(如 Google Maps)。
  2. 网络路由:最优路由规划(如 OSPF 协议)。
  3. 游戏开发:角色移动规划。
  4. 交通规划:优化物流路径。

如果需要更详细的代码示例或具体实现,可以进一步探讨!

相关文章:

Dijkstra 算法 是什么?

Dijkstra 算法 Dijkstra 算法是一种经典的最短路径算法&#xff0c;用于在图&#xff08;有向或无向图&#xff09;中找到从起点到其他所有节点的最短路径。它以广度优先搜索的方式&#xff0c;逐步扩展到目标节点&#xff0c;确保计算出的路径是最短的。 1. Dijkstra 算法的基…...

英文输入法---华为OD机试2024年E卷

题解&#xff1a; 代码&#xff1a;...

理解 package.json 中版本号符号

今天&#xff0c;聊一聊在前端开发中&#xff0c; package.json 中怎么看版本号符号。 版本号符号的解释 版本号通常由三部分组成&#xff1a;主版本号、次版本号、补丁版本号&#xff0c;格式为 major.minor.patch。常见的符号有&#xff1a; ^&#xff1a;更新时允许自动…...

计算机网络-IPSec VPN基本概念

企业分支之间经常有互联的需求&#xff0c;企业互联的方式很多&#xff0c;可以使用专线线路或者Internet线路。部分企业从成本和需求出发会选择使用Internet线路进行互联&#xff0c;但是使用Internet线路存在安全风险&#xff0c;如何保障数据在传输时不会被窃取&#xff1f;…...

VsCode运行Ts文件

1. 生成package.json文件 npm init 2. 生成tsconfig.json文件 tsc --init 3. Vscode运行ts文件 在ts文件点击右键执行Run Code,执行ts文件...

模型 AITDA(吸引、兴趣、信任、渴望、行动)

系列文章 分享 模型&#xff0c;了解更多&#x1f449; 模型_思维模型目录。吸引、兴趣、信任、渴望、行动 五步曲。 1 模型AITDA的应用 1.1 开源AI智能名片小程序的营销策略 一家企业开发了开源AI智能名片小程序&#xff0c;旨在通过S2B2C模式连接供应商和消费者。该企业采用…...

十、软件设计架构-微服务-服务调用Feign

文章目录 前言一、Feign介绍1. 什么是Feign2. 什么是Http客户端3. Feign 和 OpenFeign 的区别 二、Feign底层原理三、Feign工作原理详解1. 动态代理机制2. 动态代理的创建过程3. 创建详细流程4. FeignClient属性 四、Feign使用1. 常规调用2.日志打印3. 添加Header 前言 服务调…...

电子商务人工智能指南 3/6 - 聊天机器人和客户服务

介绍 81% 的零售业高管表示&#xff0c; AI 至少在其组织中发挥了中等至完全的作用。然而&#xff0c;78% 的受访零售业高管表示&#xff0c;很难跟上不断发展的 AI 格局。 近年来&#xff0c;电子商务团队加快了适应新客户偏好和创造卓越数字购物体验的需求。采用 AI 不再是一…...

【AI模型对比】Kimi与ChatGPT的差距:真实对比它们在六大题型中的全面表现!

文章目录 Moss前沿AI语义理解文学知识数学计算天文学知识物理学知识英语阅读理解详细对比列表总结与建议 Moss前沿AI 【OpenAI】获取OpenAI API Key的多种方式全攻略&#xff1a;从入门到精通&#xff0c;再到详解教程&#xff01;&#xff01; 【VScode】VSCode中的智能AI-G…...

spring6:2入门

spring6&#xff1a;2入门 目录 spring6&#xff1a;2入门2.1、环境要求2.2、构建模块2.3、程序开发2.3.1、引入依赖2.3.2、创建java类2.3.3、创建配置文件2.3.4、创建测试类测试2.3.5、运行测试程序 2.4、程序分析2.5、启用Log4j2日志框架2.5.1、Log4j2日志概述2.5.2、引入Log…...

Netty - NIO基础学习

一 简介 1 三大模型是什么&#xff1f; IO三大模型之一&#xff0c;BIO&#xff0c;AIO&#xff0c;还有我们的主角NIO(non-blocking-io)&#xff0c;也就是同步非阻塞式IO。这三种模型到底是干什么的&#xff1f;其实这三种模型都是对于JAVA的一种I/O框架&#xff0c;用来进行…...

ArrayList的自动扩容机制源码

Java的ArrayList的自动扩容机制 ArrayList是 Java 中极为常用的动态数组实现类&#xff0c;它依托数组存储数据&#xff0c;能依据实际需求灵活变动容量&#xff0c;高效管理元素集合。在深挖底层源码细节前&#xff0c;先来了解创建ArrayList集合并添加元素时的运作流程&#…...

【llm_inference】react框架(最小code实现)

ReAct&#xff1a;结合推理和行动的大语言模型推理架构 GitHub Code: 人人都能看懂的最小实现 引言 在人工智能领域&#xff0c;大语言模型&#xff08;LLM&#xff09;的应用日益广泛&#xff0c;但如何让模型能够像人类一样&#xff0c;在思考的基础上采取行动&#xff0c…...

PT8M2103 触控 I/O 型 8-Bit MCU

1 产品概述 ● PT8M2103 是一款可多次编程(MTP)I/O 型8位 MCU&#xff0c;其包括 2K*16bit MTP ROM、256*8bit SRAM、PWM、Touch 等功能&#xff0c;具有高性能精简指令集、低工作电压、低功耗特性且完全集成触控按键功能。为各种触控按键的应用&#xff0c;提供了一种简单而又…...

英语时态学习+名词副词形容词变形方式

开发出头不容易 不如跨界卷英语 英语中的16种时态是由四种时间&#xff08;现在、过去、将来、过去将来&#xff09;和四种体&#xff08;一般、进行、完成、完成进行&#xff09;组合而成的。以下是每种时态的详细说明和例句&#xff1a; 一般现在时 (Simple Present) 用法…...

浏览器解析页面流程

从输入一个url到页面解析完成的流程 1. 网络进程 1. 获取url 浏览器首先判断输入的url是否有http缓存&#xff0c;如果有则直接从http缓存中读取数据并显示。如果没有&#xff0c;则进行下一步。进行DNS解析&#xff0c;获取域名对应的IP地址。 2.下载html文件 浏览器根据I…...

图的遍历之DFS邻接矩阵法

本题要求实现一个函数&#xff0c;对给定的用邻接矩阵存储的无向无权图&#xff0c;以及一个顶点的编号v&#xff0c;打印以v为起点的一个深度优先搜索序列。 当搜索路径不唯一时&#xff0c;总是选取编号较小的邻接点。 本题保证输入的数据&#xff08;顶点数量、起点的编号等…...

Java --- JVM编译运行过程

目录 一.Java编译与执行流程&#xff1a; 二.编译过程&#xff1a; 1.编译器&#xff08;javac&#xff09;&#xff1a; 2.字节码文件&#xff08;.class&#xff09;&#xff1a; 三.执行过程&#xff1a; 1.启动JVM&#xff08;Java虚拟机&#xff09;&#xff1a; 2…...

HTML5 拖拽 API 深度解析

一、HTML5 拖拽 API 深度解析 1.1 背景与发展 HTML5 的拖拽 API 是为了解决传统拖拽操作复杂而设计的。传统方法依赖鼠标事件和复杂的逻辑计算&#xff0c;而 HTML5 提供了标准化的拖拽事件和数据传递机制&#xff0c;使得开发者能够快速实现从一个元素拖拽到另一个元素的交互…...

GO--基于令牌桶和漏桶的限流策略

至于为什么要限流&#xff0c;字面意思已经很清楚了&#xff0c;就是为了减轻服务器的压力 下面我们将介绍两个限流策略----漏桶和令牌桶。 漏桶 原理介绍 漏桶&#xff0c;顾名思义就是一个漏斗&#xff0c;漏斗嘴的大小是固定的&#xff0c;所以不管漏斗现容量多大&#…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

数据分析六部曲?

引言 上一章我们说到了数据分析六部曲&#xff0c;何谓六部曲呢&#xff1f; 其实啊&#xff0c;数据分析没那么难&#xff0c;只要掌握了下面这六个步骤&#xff0c;也就是数据分析六部曲&#xff0c;就算你是个啥都不懂的小白&#xff0c;也能慢慢上手做数据分析啦。 第一…...