理解 Dijkstra 算法：从理论到实现

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

什么是 Dijkstra 算法？

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

输入输出

• 输入：图表 $G=(V,E）$G=(V,E) ， 在哪里 $V$V 是顶点的集合， $E$E 是边的集合，以及源节点 V 中的 $s\epsilon V$sεV .
• 输出： 的最短路径距离 $s$s 到所有其他节点 $V$V .

核心概念

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

算法

1. 初始化距离：
   

   $$\text{距离}(s)=0,\text{距离}(v)=\mathrm{\infty }\mathrm{\forall }v\mathrm{\ne }s$$距离(s)=0,距离(v)=∞∀v=s

2. 使用优先级队列根据距离存储节点。

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

放松 - 数学解释

• 初始化： $\text{距离}(s)=0,\text{距离}(v)=\mathrm{\infty }\text{所有}v\mathrm{\ne }s$距离(s)=0,距离(v)=∞对于一个llv=s

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

• 放松步骤：对于每条边 $(u,v)$(u,v) 有重量 $w(u,v)$w(u,v) : 如果 $\text{距离}(v)>\text{距离}(u)w(u,v)$距离(v)>距离(u) w(u,v) ， 更新：
  $$\text{距离}(v)=\text{距离}(u)w(u,v),\text{上一页}(v)=u$$距离(v)=距离(u) w(u,v),上一个(v)=u

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

---

优先级队列 - 数学解释

• 队列操作：

  • 优先级队列总是使节点出列 $(u)$(u) 具有最小的暂定距离：
    $$u=\mathrm{a\; rg}\underset{v\epsilon Q}{\mathrm{分钟}}\text{距离}(v)$$u=arg v∈Q 分钟​距离(v)
  • 为什么有效：通过处理具有最小的节点 $(\text{距离}(v))$(距离(v)) ，我们保证从源到 $(u)$(u) .

---

正确性证明

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

什么是强感应？

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

Dijkstra 算法的正确性（归纳证明）

1. 基本案例：
   
   源节点 $(s)$(s) 初始化为 $\text{距离}(s)=0$距离(s)=0 ，这是正确的。

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

3. 归纳步骤:
   
   下一个节点 $(u)$(u) 从优先级队列中出列。自从 $\text{dist}(u)$距离(u) 是最小的剩余距离，并且所有先前的节点都有正确的距离， $\text{dist}(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 < distances[neighbor]) {
        distances[neighbor] = newDist; // Update the shortest distance to the neighbor
        previous[neighbor] = node; // Update the previous node
        pq.enqueue(neighbor, newDist); // Enqueue the neighbor with the updated distance
      }
    }
  }

  return { distances, previous };
}

// Example usage
const graph = {
  A: { B: 1, C: 4 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1 }
};

const result = dijkstra(graph, 'A'); // start node 'A'
console.log(result);

重建路径

// 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、C、D
• 边缘：
  • $A\to B=(1),A\to C=(4)$A→B=(1),A→C=(4)
  • $B\to C=(2),B\to D=(5)$B→C=(2),B→D=(5)
  • $C\to D=(1)$C→D=(1)

逐步执行

1. 初始化距离：
   

   $$\text{距离}(A)=0,\text{距离}(B)=\mathrm{\infty },\text{距离}(C)=\mathrm{\infty },\text{距离}(D)=\mathrm{\infty }$$距离(A)=0,距离(B)= ∞,距离(C)=∞,距离(D)=∞

2. 流程A：

   • 放松边缘： $A\to B,A\to C\mathrm{。}$A→B,A→C。
     $$\text{距离}(B)=1,\text{距离}(C)=4$$距离(B)=1,距离(C)=4

3. 过程B：

   • 放松边缘： $B\to C,B\to D\mathrm{.}$B→C,B→D。
     $$\text{距离}(C)=3,\text{距离}(D)=6$$距离(C)=3,距离(D)=6

4. 进程C：

   • 放松边缘： $C\to D\mathrm{。}$C→D.
     $$\text{距离}(D)=4$$距离(D)=4

5. 过程D：

   • 没有更多更新。

最终距离和路径

$$\text{距离}(A)=0,\text{距离}(B)=1,\text{距离}(C)=3,\text{距离}(D)=4$$距离(A)=0,距离(B)= 1,距离(C)=3,距离(D)=4

$$A\to B\to C\to 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中文网其他相关文章！