当前位置: 首页 > 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;所以不管漏斗现容量多大&#…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...