貪婪演算法經典：Dijkstra 單源最短路徑完整解析與鏈表實作

貪婪演算法經典：Dijkstra 單源最短路徑完整解析與鏈表實作

Dijkstra 演算法 以貪婪策略解決**非負邊權有向圖**的單源最短路徑問題。本文深入剖析貪婪準則、不變量證明、資料結構選擇 (無序鏈表 vs 最小堆)、完整 C++ 模板實作與複雜度分析，並對比鄰接矩陣與鄰接表表示法的效能差異。

問題定義與貪婪策略

• 輸入**：有向圖 G = (V, E)，邊權 a[u][v] ≥ 0，源點 s。
• 輸出**：d[v] = s 到 v 的最短距離；p[v] = 前驅頂點 (重建路徑用)。
• 貪婪準則**：每步從未確定集合 V \ S 中選擇 **當前估計距離 d[v] 最小** 的頂點 u 加入 S，並宣告 d[u] 為最終最短距離。

核心不變量與正確性證明

引理**：當頂點 u 被選入 S 時，d[u] = δ(s, u) (真實最短距離)。
證明 (反證法)**：假設存在更短路徑 P，則 P 必經由某頂點 y ∈ S 到 z ∉ S。但 d[z] ≤ d[y] + w(y,z) = δ(s,y) + w(y,z) = δ(s,z) < d[u]，違背 u 為最小 d 值的選擇。關鍵依賴**非負邊權**保證 d[z] ≥ d[y]。

演算法步驟 (偽碼)

1. 初始化：
   d[v] = a[s][v] (v≠s), d[s] = 0
   p[v] = s (若 a[s][v] 存在) 或 0
   L = { v | a[s][v] 存在 }  // 候選頂點集合

2. while L 不為空：
   u = argmin_{v∈L} d[v]       // 貪婪選擇
   L 移除 u
   for 每個鄰接 u 的頂點 v：
       if d[v] > d[u] + a[u][v] :  // 鬆弛
           d[v] = d[u] + a[u][v]
           p[v] = u
           if v 不在 L 中：加入 L

資料結構選擇對比

實務建議**：

• 稠密圖 (|E| ≈ |V|²)：無序陣列 O(|V|²) 反而最快 (常數因子小)。
• 稀疏圖：二元堆或配對堆平衡實作複雜度與效能。
• 邊權為小整數：桶式優先佇列 (Dial's algorithm) 線性時間。

完整 C++ 模板實作 (鄰接矩陣 + 無序鏈表)

template <class T>
void AdjacencyWDigraph<T>::ShortestPaths(int s, T d[], int p[]) {
    if (s < 1 || s > n) throw OutOfBounds();

    Chain L; ChainIterator I;
    // 初始化
    for (int i = 1; i <= n; ++i) {
        d[i] = a[s][i];
        if (d[i] == NoEdge) p[i] = 0;
        else { p[i] = s; L.Insert(0, i); }
    }

    // 主迴圈
    while (!L.IsEmpty()) {
        // 線性掃描找最小 d[v]
        int *v = I.Initialize(L);
        int *w = I.Next();
        while (w) {
            if (d[*w] < d[*v]) v = w;
            w = I.Next();
        }
        int u = *v;
        L.Delete(*v);              // 從候選集移除

        // 鬆弛所有鄰接邊
        for (int j = 1; j <= n; ++j) {
            if (a[u][j] != NoEdge && (!p[j] || d[j] > d[u] + a[u][j])) {
                d[j] = d[u] + a[u][j];
                if (!p[j]) L.Insert(0, j); // 首次發現加入候選集
                p[j] = u;
            }
        }
    }
}

路徑重建

void PrintPath(int p[], int s, int t) {
    if (t == s) { cout << s; return; }
    if (p[t] == 0) { cout << "No path"; return; }
    PrintPath(p, s, p[t]);
    cout << " -> " << t;
}

複雜度詳細分析

• 初始化**：O(|V|)。
• 主迴圈**：執行 |V| 次。
  • Extract-Min：無序鏈表 O(|L|)，總和 Σ|L| = O(|V|²)。
  • 鬆弛：鄰接矩陣掃描全列 O(|V|)，總和 O(|V|²)。
• 總計**：O(|V|²)，與鄰接矩陣表示法最優下界一致。
• 若改用鄰接表，鬆弛總時間降為 O(|E|)，但 Extract-Min 仍為 O(|V|²) (無序鏈表) 或 O(|V| log |V|) (堆)。

常見變體與延伸

• A* 搜尋**：加入啟發式 h(v)，優先佇列鍵值為 d[v] + h(v)。
• 雙向 Dijkstra**：從源點與目標點同時搜尋，相遇時終止。
• 負邊權**：Bellman-Ford (O(|V||E|)) 或 SPFA (隊列優化)。
• 全配對最短路徑**：Floyd-Warshall (O(|V|³)) 或重複跑 Dijkstra (O(|V||E| log |V|))。

結語**：Dijkstra 演算法是貪婪策略在圖論中最經典的應用，其「按距離遞增確定頂點」的不變量優雅而強大。理解資料結構對效能的決定性影響、掌握鬆弛操作的本質，是演算法工程師的必修課。