搜索
首页web前端js教程理解 Dijkstra 算法:从理论到实现

Understanding Dijkstra

Dijkstra 算法是图论中使用的经典寻路算法,用于查找图中从源节点到所有其他节点的最短路径。在本文中,我们将探索该算法、其正确性证明,并提供 JavaScript 中的实现。

什么是 Dijkstra 算法?

Dijkstra 算法是一种贪婪算法,旨在找到具有非负边权重的加权图中从单个源节点开始的最短路径。它由 Edsger W. Dijkstra 于 1956 年提出,至今仍然是计算机科学中使用最广泛的算法之一。

输入输出

  • 输入:图表 G=(V,EG = (V, E) G=(V,E) , 在哪里 VV V 是顶点的集合, EE E 是边的集合,以及源节点 V 中的 sεVV V .
  • 输出: 的最短路径距离 ss s 到所有其他节点 VV V .

核心概念

  1. 松弛:更新到节点的最短已知距离的过程。
  2. 优先队列:高效获取暂定距离最小的节点。
  3. 贪婪方法: 按照最短距离的非递减顺序处理节点。

算法

  1. 初始化距离:

    距离(s )=0,距离(v)=  vs 文本{距离}(s) = 0, 文本{距离}(v) = infty ;四方 forall v neq s 距离(s)=0,距离(v)=∞∀v=s
  2. 使用优先级队列根据距离存储节点。

  3. 反复提取距离最小的节点并松弛其邻居。

放松 - 数学解释

  • 初始化距离(s)=0,距离(v )=所有 vs文本{dist}(s) = 0, text{dist}(v) = infty , text{for all} , v neq s 距离(s)=0,距离(v)=对于一个llv=s

哪里 (s)( s ) (s) 是源节点,并且 (v)( v ) (v) 代表任何其他节点。

  • 放松步骤:对于每条边 (u,v) (u,v) (u,v) 有重量 w(u,v )w(u, v) w(u,v) : 如果 距离(v)>距离(u) w(u,v)文本{距离}(v)> text{dist}(u) w(u, v) 距离(v)>距离(u) w(u,v) , 更新:
    距离(v) =距离(u) w(u,v),上一页(v)=utext{dist}(v ) = 文本{dist}(u) w(u, v), 四边形文本{prev}(v) = u 距离(v)=距离(u) w(u,v),上一个(v)=u

为什么有效:松弛确保我们始终能够在找到更短路径时通过逐步更新距离来找到到节点的最短路径。


优先级队列 - 数学解释

  • 队列操作

    • 优先级队列总是使节点出列 (u)( u ) (u) 具有最小的暂定距离:
      u=a rg分钟 vεQ距离(v)u = arg min_{Q 中的 v} 文本{dist}(v) u=arg v∈Q 分钟距离(v)
    • 为什么有效:通过处理具有最小的节点 (距离(v) )(文本{距离}(v) ) (距离(v)) ,我们保证从源到 (u)( u ) (u) .

正确性证明

我们使用强归纳法证明了Dijkstra算法的正确性。

什么是强感应?

强归纳法是数学归纳法的一种变体,用于证明一个命题 (P(n) )( P(n) ) (P(n)) ,我们假设真相是 (P( 1),P(2),,P(k))( P(1), P(2), 点, P(k) ) (P(1),P(2),…,P(k)) 证明 (P(k 1( P(k 1) ) ( P(k 1)) 。这与常规归纳法不同,常规归纳法仅假设 (P(k) )( P(k) ) (P(k)) 证明 (P(k 1( P(k 1) ) ( P(k 1)) 。在我的另一篇文章中更详细地探索它。

Dijkstra 算法的正确性(归纳证明)

  1. 基本案例

    源节点 (s)( s ) (s) 初始化为 距离(s)=0文本{dist}(s) = 0 距离(s)=0 ,这是正确的。

  2. 归纳假设:

    假设到目前为止处理的所有节点都有正确的最短路径距离。

  3. 归纳步骤:

    下一个节点 (u)( u ) (u) 从优先级队列中出列。自从 dist(u)text{dist} (你) 距离(u) 是最小的剩余距离,并且所有先前的节点都有正确的距离, dist(u)text{dist} (你) 距离(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,DA, B、C、D A、B、C、D
  • 边缘:
    • AB=( 1),AC=(4)A至 B = (1),A 至 C = (4) A→B=(1),A→C=(4)
    • BC=( 2),BD=(5)B至 C = (2),B 至 D = (5) B→C=(2),B→D=(5)
    • CD=(1)C至 D = (1) C→D=(1)

逐步执行

  1. 初始化距离:

    距离(A)= 0 ,  距离(B)=,  距离(C)=,  距离(D)= 文本{距离}(A) = 0, ;文本{距离}(B) = infty, ;文本{距离}(C) = infty, ;文本{距离}(D) = infty 距离(A)=0,距离(B)= ∞,距离(C)=∞,距离(D)=
  2. 流程A:

    • 放松边缘: AB,ACA到 B,A 到 C。A→B,A→C。
      距离(B)=1,  距离(C)=4文本{距离}(B) = 1,;文本{距离}(C) = 4 距离(B)=1,距离(C)=4
  3. 过程B:

    • 放松边缘: BC,BD.B到 C,B 到 D。B→C,B→D。
      距离(C)=3,  距离(D)=6文本{距离}(C) = 3,;文本{距离}(D) = 6 距离(C)=3,距离(D)=6
  4. 进程C:

    • 放松边缘: CDC 到 D。 C→D.
      距离(D)=4文本{dist}(D) = 4 距离(D)=4
  5. 过程D:

    • 没有更多更新。

最终距离和路径

距离(A)= 0 ,  距离(B)=1,  距离(C)= 3,  距离(D)=4 文本{距离}(A) = 0, ;文本{距离}(B) = 1, ;文本{距离}(C) = 3, ;文本{距离}(D) = 4 距离(A)=0,距离(B)= 1,距离(C)=3,距离(D)=4

AB CD A 到 B 到 C 到 D A→B→C→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)

要点:

  1. 简单数组
    • 由于提取最小值的线性搜索,对于大图来说效率低下。
  2. 二叉堆
    • 由于其简单性和效率的平衡而成为标准和常用的。
  3. 二项式堆
    • 理论保证稍好,但实现起来更复杂。
  4. 斐波那契堆
    • ( O(1) )摊销递减密钥的最佳理论性能,但更难实现。
  5. 配对堆
    • 简单并且在实践中表现接近斐波那契堆。

结论

Dijkstra 算法是一种强大而有效的方法,用于在具有非负权重的图中查找最短路径。虽然它有局限性(例如,无法处理负边权重),但它广泛用于网络、路由和其他应用程序。

  • 松弛通过迭代更新路径确保最短距离。
  • 优先队列保证我们总是处理最近的节点,保持正确性。
  • 正确性通过归纳法证明:一旦节点的距离确定,它就保证是最短路径。

这里有一些详细的资源,您可以在其中探索 Dijkstra 算法以及严格的证明和示例:

  • Dijkstra 算法 PDF
  • SlideShare 上的最短路径算法

此外,维基百科提供了该主题的精彩概述。

引用:
[1] https://www.fuhuthu.com/CPSC420F2019/dijkstra.pdf

欢迎在评论中分享您的想法或改进!

以上是理解 Dijkstra 算法:从理论到实现的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
node.js流带打字稿node.js流带打字稿Apr 30, 2025 am 08:22 AM

Node.js擅长于高效I/O,这在很大程度上要归功于流。 流媒体汇总处理数据,避免内存过载 - 大型文件,网络任务和实时应用程序的理想。将流与打字稿的类型安全结合起来创建POWE

Python vs. JavaScript:性能和效率注意事项Python vs. JavaScript:性能和效率注意事项Apr 30, 2025 am 12:08 AM

Python和JavaScript在性能和效率方面的差异主要体现在:1)Python作为解释型语言,运行速度较慢,但开发效率高,适合快速原型开发;2)JavaScript在浏览器中受限于单线程,但在Node.js中可利用多线程和异步I/O提升性能,两者在实际项目中各有优势。

JavaScript的起源:探索其实施语言JavaScript的起源:探索其实施语言Apr 29, 2025 am 12:51 AM

JavaScript起源于1995年,由布兰登·艾克创造,实现语言为C语言。1.C语言为JavaScript提供了高性能和系统级编程能力。2.JavaScript的内存管理和性能优化依赖于C语言。3.C语言的跨平台特性帮助JavaScript在不同操作系统上高效运行。

幕后:什么语言能力JavaScript?幕后:什么语言能力JavaScript?Apr 28, 2025 am 12:01 AM

JavaScript在浏览器和Node.js环境中运行,依赖JavaScript引擎解析和执行代码。1)解析阶段生成抽象语法树(AST);2)编译阶段将AST转换为字节码或机器码;3)执行阶段执行编译后的代码。

Python和JavaScript的未来:趋势和预测Python和JavaScript的未来:趋势和预测Apr 27, 2025 am 12:21 AM

Python和JavaScript的未来趋势包括:1.Python将巩固在科学计算和AI领域的地位,2.JavaScript将推动Web技术发展,3.跨平台开发将成为热门,4.性能优化将是重点。两者都将继续在各自领域扩展应用场景,并在性能上有更多突破。

Python vs. JavaScript:开发环境和工具Python vs. JavaScript:开发环境和工具Apr 26, 2025 am 12:09 AM

Python和JavaScript在开发环境上的选择都很重要。1)Python的开发环境包括PyCharm、JupyterNotebook和Anaconda,适合数据科学和快速原型开发。2)JavaScript的开发环境包括Node.js、VSCode和Webpack,适用于前端和后端开发。根据项目需求选择合适的工具可以提高开发效率和项目成功率。

JavaScript是用C编写的吗?检查证据JavaScript是用C编写的吗?检查证据Apr 25, 2025 am 12:15 AM

是的,JavaScript的引擎核心是用C语言编写的。1)C语言提供了高效性能和底层控制,适合JavaScript引擎的开发。2)以V8引擎为例,其核心用C 编写,结合了C的效率和面向对象特性。3)JavaScript引擎的工作原理包括解析、编译和执行,C语言在这些过程中发挥关键作用。

JavaScript的角色:使网络交互和动态JavaScript的角色:使网络交互和动态Apr 24, 2025 am 12:12 AM

JavaScript是现代网站的核心,因为它增强了网页的交互性和动态性。1)它允许在不刷新页面的情况下改变内容,2)通过DOMAPI操作网页,3)支持复杂的交互效果如动画和拖放,4)优化性能和最佳实践提高用户体验。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境