經典算法研究：徹底理解Dijkstra算法——從單源最短路徑到斐波那契堆優化

本文承接上篇，深入剖析Dijkstra算法每一步執行細節，重點講解鬆弛技術、三種優先隊列的具體操作差異，並完整推導斐波那契堆實現的O(V log V + E)複雜度來源。

一、 單源最短路徑問題變體

• 單源最短路徑：源點s到所有v∈V。
• 單終點最短路徑：所有v到終點t（反向圖跑單源）。
• 單對最短路徑：指定u→v（A*更優）。
• 全對最短路徑：Floyd-Warshall或跑V次單源。

二、 Bellman-Ford 算法回顧（負權邊基準）

BELLMAN-FORD(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  for i ← 1 to |V|-1
3      for each edge (u,v) ∈ E
4          RELAX(u, v, w)
5  for each edge (u,v) ∈ E
6      if d[v] > d[u] + w(u,v)  return FALSE  // 存在負權環
7  return TRUE

時間O(VE)。核心結論：無負權環 ⇔ 所有邊滿足 d[v] ≤ d[u] + w(u,v)（三角不等式）。Dijkstra要求非負權，正是為了避開負環複雜性，換取O(E log V)效率。

三、 Dijkstra 算法逐步解剖

1. INITIALIZE-SINGLE-SOURCE

for each v ∈ V: d[v] ← ∞, π[v] ← NIL
d[s] ← 0

O(V)。建立「最短路徑估計」上界與前驅記錄。

2. 優先隊列 Q 初始化

Q ← V[G]  // 所有頂點入隊，鍵值為 d[v]

此步差異決定後續複雜度：

• 數組：O(V) 建堆，但EXTRACT-MIN需O(V)掃描。
• 二叉堆：O(V) 建堆（自底向上），EXTRACT-MIN O(log V)。
• 斐波那契堆：O(V) 插入（各O(1)），EXTRACT-MIN O(log V) 平攤。

3. 主循環：EXTRACT-MIN + RELAX

while Q ≠ ∅:
    u ← EXTRACT-MIN(Q)      // 確定 u 的最短路徑
    S ← S ∪ {u}
    for each v ∈ Adj[u]:
        RELAX(u, v, w)      // 可能觸發 DECREASE-KEY

關鍵不變量：S中頂點的d值為真實最短距離，不再改變。

四、 三種優先隊列操作對比表

五、 斐波那契堆優化細節

斐波那契堆通過延遲合併、標記機制、度數界實現DECREASE-KEY攤銷O(1)。Dijkstra中每條邊最多觸發一次DECREASE-KEY，故總貢獻O(E)。
EXTRACT-MIN需合併樹根鏈表、合併同度樹，攤銷O(log V)，共V次，貢獻O(V log V)。

六、 何時選擇斐波那契堆？

當|V| ≪ |E|（極稀疏圖）且極度追求理論上界時。工程實踐中，二叉堆/配對堆常數更小、實現更簡，往往更快。理解其原理比直接套用更重要。

下篇將給出基於二叉堆的完整C語言實現源碼，含圖結構、堆操作、路徑回溯，可直接編譯運行。