Dijkstra算法是單源最短路徑問題的經典解法，適用於非負權圖。本文系統梳理算法邏輯、三種優先隊列實現的複雜度對比、圖文演示步驟，並關聯Prim、BFS等同類算法。
給定有向圖G=(V,E)、權重函數w: E→[0,∞)、源點s。求s到所有頂點的最短路徑。
核心思想：貪心—— 每次從未確定集合中選取距離源點最近的頂點u，宣告其最短路徑已確定，並以此「鬆弛」出邊。
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s) // d[v]=∞, π[v]=NIL, d[s]=0
2 S ← ∅
3 Q ← V[G] // 優先隊列，鍵值為 d[v]
4 while Q ≠ ∅
5 u ← EXTRACT-MIN(Q) // 取距離最小頂點
6 S ← S ∪ {u}
7 for each v ∈ Adj[u] // 鬆弛出邊
8 do RELAX(u, v, w)
RELAX(u, v, w)
if d[v] > d[u] + w(u,v)
d[v] ← d[u] + w(u,v)
π[v] ← u
| 實現方式 | EXTRACT-MIN | DECREASE-KEY | 總時間 | 適用場景 |
|---|---|---|---|---|
| 數組/鏈表 | O(V) | O(1) | O(V²+E) | 稠密圖、教學演示 |
| 二叉堆 | O(log V) | O(log V) | O((V+E)log V) ≈ O(E log V) | 稀疏圖、通用首選 |
| 斐波那契堆 | O(log V) | O(1) 平攤 | O(V log V + E) | 理論最優、E ≫ V 時優勢明顯 |
稀疏圖E=O(V²/log V)時，二叉堆退化至O(V²)；斐波那契堆始終保持O(V log V + E)。
源點 A，求到 B/C/D/E/F 最短路徑。算法以 A 為中心向外層層擴展，每輪鎖定一個頂點。
| 輪次 | S (已確定) | Q 中 d 值變化 | EXTRACT-MIN |
|---|---|---|---|
| 0 | ∅ | A:0, B:∞, C:∞, D:∞, E:∞, F:∞ | A (d=0) |
| 1 | {A} | C:3, B:6, D:∞, E:∞, F:∞ | C (d=3) |
| 2 | {A,C} | B:5, D:6, E:7, F:∞ | B (d=5) |
| 3 | {A,C,B} | D:6, E:7, F:9 | D (d=6) |
| 4 | {A,C,B,D} | E:7, F:9 | E (d=7) |
| 5 | {A,C,B,D,E} | F:9 | F (d=9) |
最終最短路徑：A→C→B(5)、A→C(3)、A→C→D(6)、A→C→E(7)、A→C→D→F(9)。
O(VE)，可檢測負環。h(n)啟發，單對最短路徑更快。| 算法 | 時間複雜度 | 備註 |
|---|---|---|
| BFS/DFS | O(V+E) | 無權圖 |
| Kruskal | O(E log V) | 最小生成樹 |
| Prim (斐波那契堆) | O(E + V log V) | 稠密圖優勢大 |
| Dijkstra (斐波那契堆) | O(V log V + E) | 與Prim同級 |
掌握 Dijkstra 的鬆弛框架與優先隊列選型，即掌握了加權圖最短路徑的通用解法。
