理解 Dijkstra 演算法：從理論到實現

Dijkstra 演算法是圖論中使用的經典尋路演算法，用於尋找圖中從來源節點到所有其他節點的最短路徑。在本文中，我們將探索該演算法、其正確性證明，並提供 JavaScript 中的實作。

什麼是 Dijkstra 演算法？

Dijkstra 演算法是一種貪婪演算法，旨在找到具有非負邊權重的加權圖中從單一來源節點開始的最短路徑。它由 Edsger W. Dijkstra 於 1956 年提出，至今仍然是電腦科學中使用最廣泛的演算法之一。

輸入輸出

• 輸入：圖表 $G=(V,E）$G=(V,E) ， 在哪裡 $V$VV$$VV$V是頂點的集合，E$E E
• EE > 是邊的集合，以及源節點 V 中的 $s$VV sε$V.輸出：$ 的最短路徑距離 s

1. s
2. s
3. 到所有其他節點

1. V

   
   

   VVVVVVV . 核心概念 鬆弛：更新到節點的最短已知距離的過程。 優先隊列：高效率取得暫定距離最小的節點。 貪婪法： 依照最短距離的非遞減順序處理節點。 演算法 初始化距離：
   $$\text{距離}(s)=0,\text{距離}(v)=\mathrm{\infty }\mathrm{\forall }v\mathrm{\ne }s$$距離(s)=0,距離(v)=距離(v)=(v)=(v)=∞∀v
   =s

2. 使用優先權佇列根據距離儲存節點。

3. 重複提取距離最小的節點並鬆弛其鄰居。

放鬆 - 數學解釋

• 初始化： $\text{距離}(s)=0,\text{距離}(v)=\mathrm{\infty }\text{所有}v\mathrm{\ne }s$距離(s)=0,距離(v)=距離(v)=(v)=(v)=∞對於一個llv

s$哪裡$(s)( s ) $(s)是源節點，並且$(v)( v )

• 放鬆步驟：對於每條邊 $(u,v$（u，v） (u,v)$w(u,,$v)w(u, v) $:\; 如果距離\text{(}v)v)>距離(u)($u,v)v)v
  )v(u,v),上一頁(v
  )=距離(v)=距離(u) w(u,v),上一個(v)=u

為什麼有效：鬆弛確保我們始終能夠在找到更短路徑時透過逐步更新距離來找到到節點的最短路徑。

優先權隊列 - 數學解釋

• 隊列操作：

  • 優先權佇列總是使節點出列 $(u)$(u) 最小的暫定距離：
    $$u=\mathrm{a\; rg}\underset{v\epsilon Q}{\mathrm{分鐘}}\text{距離}(v)$$u=arg v∈Q 分鐘距離距離距離
  • 為什麼有效：透過處理具有最小的節點 $(\text{距離}(v(v$(文本{距離}(v) ) (距離(v)) $，我們保證從源頭到(u$( u ) (u)
.

正確性證明

什麼是強感應？

強歸納法是數學歸納法的變體，用來證明一個命題 $(P(n(n$( P(n) ) (P(n))$(\mathrm{P}(1),\mathrm{P}(2),\dots ,P(k)$( P(1), P(2), 點, P (k) ) (P(1),P(2),…,P(k)) $(P(\mathrm{k}(kk$kk$kkkd1$)( P(k 1) ) (>(>$1))($k)( P(k) )

(P(k))

1. 證明
   
   ($(k($kk$kkkk\mathrm{}$1）)( P(k 1) )

   (>(>1)) 。在我的另一篇文章中更詳細地探索它。 Dijkstra 演算法的正確性（歸納證明） 基本案例： 來源節點 (s)( s ) (s) 初始化為 距離(s)=0文字{dist}(s) = 0 距離(s)=0 ，這是正確的。

2. 歸納假設:
   
   假設到目前為止處理的所有節點都有正確的最短路徑距離。

3. 歸納步驟:
   
   下一個節點 $(u)$(u) 從優先權佇列中出列。自從 $\text{dist}(u))$u)距離(u)$\text{是最小的剩餘距離，並且所有先前的節點都有正確的距離，}distu$)u)u

   )

距離
(u)

// 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;
  }
}

也是正確的。

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=\mathrm{=}1),A\to C\mathrm{=}()$A至 B = (1)，A 至 C = (4) A→B=(1),A→C=(1),A→
  C=
  • >(4)$B\mathrm{\to }C=C=2)\mathrm{,}BD$=(5)B至 C = (2)，B 至 D = (5) B→
  • C=(2),B→$(2),B\to D=\mathrm{>(5)}\mathrm{}C$→D=(1
  )
C至 D = (1)

1. C→

   
   D=

   (1)$$逐步執行初始化距離：\mathrm{}\text{距離}(A)A\mathrm{)}\text{0}\text{,}\hspace{0.25em} \mathrm{距離}(B\mathrm{)}B\text{)}))\mathrm{）\infty }\hspace{0.25em}$$距離(C)C)C))
   ) ∞,  距離(D)D)>D)>>>>某事> 文字{距離}(A) = 0, ;文字{距離}(B) = infty, ;文字{距離}(C) = infty, ;文字{距離}(D) = infty 距離(A)=0,距離(B)=距離(B)=(B)= > ∞,距離(C)=∞,距離(D)=∞

2. 流程A：

   • 放鬆邊緣： $A\to B,A\to C\mathrm{。}$A→B,A→C。
     $$\text{距離}(B)=1,\text{距離}(C)=\mathrm{)}$$距離(B)=1,距離(C)=(C)=(C)=
   (C)=

3. >4

   • $過程B：\mathrm{放鬆邊緣：}B\to \mathrm{C}B$→D.B到 C，B 到 D。
     B→$$C,B\to D。\mathrm{距離}(\text{C}\text{)}=3,\hspace{0.25em} \mathrm{距離}D$$)=)文字{距離}(C) = 3,;文本{距離}(D) = 6 距離(C)=
   3,
   距離
(D)=

4. (D)=
   • (D)=$6\mathrm{}進程C：$ 放鬆邊緣： C
     →$$D。C\; 到\; D。C\to D.\mathrm{}$$距離(D)
     =4文字{dist}(D) = 4 距離(D)=4

5. 過程D：

   • 沒有更多更新。

最終距離和路徑

要點：

1. 簡單數組：
   • 由於提取最小值的線性搜索，對於大圖來說效率低下。
2. 二元堆：
   • 由於其簡單性和效率的平衡而成為標準和常用的。
3. 二項式堆：
   • 理論保證稍好，但實現起來更複雜。
4. 斐波那契堆：
   • （ O(1) ）攤銷遞減金鑰的最佳理論效能，但更難實現。
5. 配對堆：
   • 簡單且在實務上表現接近斐波那契堆。

結論

Dijkstra 演算法是一種強大而有效的方法，用於在具有非負權重的圖中找到最短路徑。雖然它有限制（例如，無法處理負邊權重），但它廣泛用於網路、路由和其他應用程式。

• 鬆弛透過迭代更新路徑確保最短距離。
• 優先隊列保證我們總是處理最近的節點，保持正確性。
• 正確性用歸納法證明：一旦節點的距離確定，它就保證是最短路徑。

這裡有一些詳細的資源，您可以在其中探索 Dijkstra 演算法以及嚴格的證明和範例：

• Dijkstra 演算法 PDF
• SlideShare 上的最短路徑演算法

此外，維基百科提供了該主題的精彩概述。

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

歡迎在評論中分享您的想法或改進！

以上是理解 Dijkstra 演算法：從理論到實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！