Dijkstra 算法是图论中使用的经典寻路算法,用于查找图中从源节点到所有其他节点的最短路径。在本文中,我们将探索该算法、其正确性证明,并提供 JavaScript 中的实现。
什么是 Dijkstra 算法?
Dijkstra 算法是一种贪婪算法,旨在找到具有非负边权重的加权图中从单个源节点开始的最短路径。它由 Edsger W. Dijkstra 于 1956 年提出,至今仍然是计算机科学中使用最广泛的算法之一。
输入输出
- 输入:图表 G=(V,E) , 在哪里 V 是顶点的集合, E 是边的集合,以及源节点 V 中的 sεV .
- 输出: 的最短路径距离 s 到所有其他节点 V .
核心概念
- 松弛:更新到节点的最短已知距离的过程。
- 优先队列:高效获取暂定距离最小的节点。
- 贪婪方法: 按照最短距离的非递减顺序处理节点。
算法
-
初始化距离:
距离(s)=0,距离(v)=∞∀v=s 使用优先级队列根据距离存储节点。
反复提取距离最小的节点并松弛其邻居。
放松 - 数学解释
- 初始化: 距离(s)=0,距离(v)=∞对于一个llv=s
哪里 (s) 是源节点,并且 (v) 代表任何其他节点。
-
放松步骤:对于每条边
(u,v)
有重量
w(u,v)
:
如果
距离(v)>距离(u) w(u,v)
, 更新:
距离(v)=距离(u) w(u,v),上一个(v)=u
为什么有效:松弛确保我们始终能够在找到更短路径时通过逐步更新距离来找到到节点的最短路径。
优先级队列 - 数学解释
-
队列操作:
- 优先级队列总是使节点出列
(u)
具有最小的暂定距离:
u=arg v∈Q 分钟距离(v)
- 为什么有效:通过处理具有最小的节点 (距离(v)) ,我们保证从源到 (u) .
- 优先级队列总是使节点出列
(u)
具有最小的暂定距离:
正确性证明
我们使用强归纳法证明了Dijkstra算法的正确性。
什么是强感应?
强归纳法是数学归纳法的一种变体,用于证明一个命题 (P(n)) ,我们假设真相是 (P(1),P(2),…,P(k)) 证明 ( P(k 1)) 。这与常规归纳法不同,常规归纳法仅假设 (P(k)) 证明 ( P(k 1)) 。在我的另一篇文章中更详细地探索它。
Dijkstra 算法的正确性(归纳证明)
基本案例:
源节点 (s) 初始化为 距离(s)=0 ,这是正确的。归纳假设:
假设到目前为止处理的所有节点都有正确的最短路径距离。归纳步骤:
下一个节点 (u) 从优先级队列中出列。自从 距离(u) 是最小的剩余距离,并且所有先前的节点都有正确的距离, 距离(u) 也是正确的。
JavaScript 实现
先决条件(优先队列):
// Simplified Queue using Sorting // Use Binary Heap (good) // or Binomial Heap (better) or Pairing Heap (best) class PriorityQueue { constructor() { this.queue = []; } enqueue(node, priority) { this.queue.push({ node, priority }); this.queue.sort((a, b) => a.priority - b.priority); } dequeue() { return this.queue.shift(); } isEmpty() { return this.queue.length === 0; } }
这是使用优先级队列的 Dijkstra 算法的 JavaScript 实现:
function dijkstra(graph, start) { const distances = {}; // hold the shortest distance from the start node to all other nodes const previous = {}; // Stores the previous node for each node in the shortest path (used to reconstruct the path later). const pq = new PriorityQueue(); // Used to efficiently retrieve the node with the smallest tentative distance. // Initialize distances and previous for (let node in graph) { distances[node] = Infinity; // Start with infinite distances previous[node] = null; // No previous nodes at the start } distances[start] = 0; // Distance to the start node is 0 pq.enqueue(start, 0); while (!pq.isEmpty()) { const { node } = pq.dequeue(); // Get the node with the smallest tentative distance for (let neighbor in graph[node]) { const distance = graph[node][neighbor]; // The edge weight const newDist = distances[node] + distance; // Relaxation Step if (newDist重建路径
// Simplified Queue using Sorting // Use Binary Heap (good) // or Binomial Heap (better) or Pairing Heap (best) class PriorityQueue { constructor() { this.queue = []; } enqueue(node, priority) { this.queue.push({ node, priority }); this.queue.sort((a, b) => a.priority - b.priority); } dequeue() { return this.queue.shift(); } isEmpty() { return this.queue.length === 0; } }示例演练
图形表示
- 节点: A、B、C、D
-
边缘:
- A→B=(1),A→C=(4)
- B→C=(2),B→D=(5)
- C→D=(1)
逐步执行
-
初始化距离:
距离(A)=0,距离(B)= ∞,距离(C)=∞,距离(D)=∞ -
流程A:
- 放松边缘:
A→B,A→C。
距离(B)=1,距离(C)=4
- 放松边缘:
A→B,A→C。
-
过程B:
- 放松边缘:
B→C,B→D。
距离(C)=3,距离(D)=6
- 放松边缘:
B→C,B→D。
-
进程C:
- 放松边缘:
C→D.
距离(D)=4
- 放松边缘:
C→D.
-
过程D:
- 没有更多更新。
最终距离和路径
优化和时间复杂度
比较 Dijkstra 算法与不同优先级队列实现的时间复杂度:
Priority Queue Type | Insert (M) | Extract Min | Decrease Key | Overall Time Complexity |
---|---|---|---|---|
Simple Array | O(1) | O(V) | O(V) | O(V^2) |
Binary Heap | O(log V) | O(log V) | O(log V) | O((V E) log V) |
Binomial Heap | O(log V) | O(log V) | O(log V) | O((V E) log V) |
Fibonacci Heap | O(1) | O(log V) | O(1) | O(V log V E) |
Pairing Heap | O(1) | O(log V) | O(log V) | O(V log V E) (practical) |
要点:
-
简单数组:
- 由于提取最小值的线性搜索,对于大图来说效率低下。
-
二叉堆:
- 由于其简单性和效率的平衡而成为标准和常用的。
-
二项式堆:
- 理论保证稍好,但实现起来更复杂。
-
斐波那契堆:
- ( O(1) )摊销递减密钥的最佳理论性能,但更难实现。
-
配对堆:
- 简单并且在实践中表现接近斐波那契堆。
结论
Dijkstra 算法是一种强大而有效的方法,用于在具有非负权重的图中查找最短路径。虽然它有局限性(例如,无法处理负边权重),但它广泛用于网络、路由和其他应用程序。
- 松弛通过迭代更新路径确保最短距离。
- 优先队列保证我们总是处理最近的节点,保持正确性。
- 正确性通过归纳法证明:一旦节点的距离确定,它就保证是最短路径。
这里有一些详细的资源,您可以在其中探索 Dijkstra 算法以及严格的证明和示例:
- Dijkstra 算法 PDF
- SlideShare 上的最短路径算法
此外,维基百科提供了该主题的精彩概述。
引用:
[1] https://www.fuhuthu.com/CPSC420F2019/dijkstra.pdf
欢迎在评论中分享您的想法或改进!
以上是理解 Dijkstra 算法:从理论到实现的详细内容。更多信息请关注PHP中文网其他相关文章!

JavaScript字符串替换方法详解及常见问题解答 本文将探讨两种在JavaScript中替换字符串字符的方法:在JavaScript代码内部替换和在网页HTML内部替换。 在JavaScript代码内部替换字符串 最直接的方法是使用replace()方法: str = str.replace("find","replace"); 该方法仅替换第一个匹配项。要替换所有匹配项,需使用正则表达式并添加全局标志g: str = str.replace(/fi

利用轻松的网页布局:8个基本插件 jQuery大大简化了网页布局。 本文重点介绍了简化该过程的八个功能强大的JQuery插件,对于手动网站创建特别有用

因此,在这里,您准备好了解所有称为Ajax的东西。但是,到底是什么? AJAX一词是指用于创建动态,交互式Web内容的一系列宽松的技术。 Ajax一词,最初由Jesse J创造

本教程演示了创建通过Ajax加载的动态页面框,从而可以即时刷新,而无需全页重新加载。 它利用jQuery和JavaScript。将其视为自定义的Facebook式内容框加载程序。 关键概念: Ajax和JQuery

10款趣味横生的jQuery游戏插件,让您的网站更具吸引力,提升用户粘性!虽然Flash仍然是开发休闲网页游戏的最佳软件,但jQuery也能创造出令人惊喜的效果,虽然无法与纯动作Flash游戏媲美,但在某些情况下,您也能在浏览器中获得意想不到的乐趣。 jQuery井字棋游戏 游戏编程的“Hello world”,现在有了jQuery版本。 源码 jQuery疯狂填词游戏 这是一个填空游戏,由于不知道单词的上下文,可能会产生一些古怪的结果。 源码 jQuery扫雷游戏

此JavaScript库利用窗口。名称属性可以管理会话数据,而无需依赖cookie。 它为浏览器中存储和检索会话变量提供了强大的解决方案。 库提供了三种核心方法:会话

本教程演示了如何使用jQuery创建迷人的视差背景效果。 我们将构建一个带有分层图像的标题横幅,从而创造出令人惊叹的视觉深度。 更新的插件可与JQuery 1.6.4及更高版本一起使用。 下载


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

MinGW - 适用于 Windows 的极简 GNU
这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

SublimeText3 Linux新版
SublimeText3 Linux最新版

适用于 Eclipse 的 SAP NetWeaver 服务器适配器
将Eclipse与SAP NetWeaver应用服务器集成。