Dijkstra 最短路徑

🎯 什麼情境該想到我

當你「邊有不同的成本，要找總成本最低的路徑」的時候——導航、網路路由、遊戲尋路、最便宜轉機。
★ 它的正確性完全建立在「邊權非負」上。 這頁會用一個具體反例說明為什麼——那是這題的必考點。

⚙️ 怎麼用（機制、證明與實作）

核心：貪婪 + 鬆弛

1. dist[s] = 0，其餘 = ∞
2. 重複：
   a. ★ 從「尚未確定」的點中取出 dist 最小的 u  → 宣告 dist[u] 為最終答案
   b. 對 u 的每條出邊 (u,v,w) 做「鬆弛」：
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

「鬆弛（relax）」的意思：「繞過 u 走到 v，會不會比目前已知的路更短？」

★ 正確性：為什麼「取出即最終」

不變式：當 $u$ 被取出時，dist[u] 已是真正的最短距離。

反證：假設存在一條更短的路 $P$ 到 $u$ 。 $P$ 上必有第一個「尚未確定」的點 $x$ （可能就是 $u$ ）。
那麼 $dist [x] \leq$ （ $P$ 上到 $x$ 的長度） $\leq$ （ $P$ 的總長） $<$ dist[u]。
但我們是取 dist 最小的才取出 $u$ ，矛盾。

★ 第二個 $\leq$ 的成立，完全依賴「從 $x$ 到 $u$ 的那一段長度 $\geq 0$ 」——
也就是邊權非負。 這就是整個演算法的命脈。

★ 負權為什麼會錯（一個具體反例）

      1
  S ──────▶ A
  │          ▲
  │2         │ -2
  ▼          │
  B ─────────┘

真正的最短距離：dist[A] = min(1, 2 + (-2)) = 0   （走 S→B→A）

Dijkstra 的執行：

取出 S(0)  → 鬆弛：dist[A]=1, dist[B]=2
取出 A(1)  → ★ A 被「確定」為 1
取出 B(2)  → 鬆弛 B→A：2 + (-2) = 0 < 1
              但 A 已經被確定了 —— 標準實作不會再更新
結果 dist[A] = 1   ❌ 錯（正確是 0）

★ 問題的本質：負邊讓「後來才發現的路」有可能更短，違反了「取出即最終」的前提。
有負權 → 用 Bellman-Ford 最短路徑（它不做「確定」這件事，而是反覆鬆弛所有邊）。

Go 實作（堆優化）

import "container/heap"
 
type item struct{ node, dist int }
 
func Dijkstra(adj [][]edge, n, s int) []int {
    const INF = math.MaxInt / 2
    dist := make([]int, n)
    for i := range dist { dist[i] = INF }
    dist[s] = 0
 
    pq := &minHeap{{s, 0}}                 // 見 [[二元堆積]]
    heap.Init(pq)
    for pq.Len() > 0 {
        it := heap.Pop(pq).(item)
        // ★ 惰性刪除：堆裡可能有同一個節點的舊（較大）記錄，直接跳過
        if it.dist > dist[it.node] { continue }
        for _, e := range adj[it.node] {
            if nd := it.dist + e.w; nd < dist[e.to] {
                dist[e.to] = nd
                heap.Push(pq, item{e.to, nd})   // ★ 推入新記錄，不去改舊的
            }
        }
    }
    return dist
}

★ 「惰性刪除」是實務上的標準做法：
二元堆不支援「更新某個既有元素的鍵」（decrease-key），要做到得額外維護 map[node]index 並呼叫 heap.Fix。
更簡單的做法是直接推入新記錄，取出時用 it.dist > dist[it.node] 過濾掉過時的。
代價是堆最大會到 $O (E)$ ，但實作簡單太多且實測更快。

複雜度

實作	複雜度	適合
陣列（每次線性找最小）	$O (V^{2})$	稠密圖（ $E \approx V^{2}$ ）
二元堆 + 惰性刪除	$O (E lo g V)$	★ 稀疏圖，實務預設
Fibonacci heap	$O (E + V lo g V)$	理論最優，實務上常數太大沒人用

變體與相鄰演算法

情況	用什麼
無權圖（或所有邊權相同）	★ 廣度優先搜尋， $O (V + E)$ ——別用 Dijkstra
邊權只有 0 和 1	0-1 BFS（雙端佇列）， $O (V + E)$
有負權	Bellman-Ford 最短路徑
所有點對	Floyd-Warshall 全對最短路（稠密）或跑 $V$ 次 Dijkstra（稀疏）
有啟發資訊（如地理距離）	A：把優先序改成 `dist + h(v)`。h 必須可採納（不高估）才保證最佳*
只要單一終點	找到終點就可以提前 return

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 負權邊會給出錯誤答案，而且不會報錯（見上面的反例）。用之前先確認邊權全部 ≥ 0。
★ 無權圖不要用 Dijkstra。BFS 是 $O (V + E)$ 且沒有堆的開銷。
INF 用 math.MaxInt 會溢位：INF + w 會變成負數。用 math.MaxInt / 2 或在鬆弛前檢查 dist[u] != INF。
要輸出路徑不只是距離時要記 parent[]。
稠密圖上 $O (V^{2})$ 的陣列版可能更快（沒有堆的常數與配置）。
動態變化的圖（邊權一直改）要重跑；增量式最短路（D* Lite 等）複雜得多。
Go 的 container/heap 沒有泛型，熱路徑上可自己寫一個泛型堆省掉 any 的裝箱。

🔗 相關工具

Bellman-Ford 最短路徑 —— 有負權時的替代方案
廣度優先搜尋 —— 無權圖的特例（也更快）
Floyd-Warshall 全對最短路 —— 所有點對
二元堆積 —— 優先佇列的實作與 heap.Fix
貪婪演算法 —— Dijkstra 是有嚴格證明的貪婪
Prim 最小生成樹 —— 結構幾乎一樣，只差鬆弛的定義
演算法導論

Quartz 5

Explorer