Learning Objectives
- 說明有權重的圖裡，「經過的邊最少」不等於「權重總和最小」，所以 BFS 不夠用
- 說明鬆弛（relaxation）在做什麼，並追蹤 dist 與 parent 怎麼被更新
- 用優先佇列（最小堆積存 (距離, 節點)）實作 Dijkstra 演算法，處理佇列裡的舊紀錄
- 用 parent 還原最短路徑
- 用小例子說明負權重為什麼會讓 Dijkstra 出錯，並用 Bellman-Ford 算出正確答案、偵測負環
邊有了長短
導航軟體在找路時，關心的不是「經過幾個路口」，而是「總共要花幾分鐘」。每條路的時間不一樣， 這種邊上帶著數字的圖叫做有權重的圖（weighted graph），一條路徑的長度是路上所有邊的權重總和。
上一課的 BFS 在這裡不夠用。看這個例子：
A --10-- B
\ /
1 1
\ /
C
BFS 會說 A 到 B 最近，因為只要 1 條邊；但走 A → C → B 只要 1 + 1 = 2，比直接走的 10 短得多。 「邊最少」和「權重總和最小」是兩回事。
這一課的主角是 Dijkstra 演算法：荷蘭計算機科學家 Edsger W. Dijkstra 在 1959 年發表， 用來找「從一個起點到其他所有節點」的最短路徑，前提是所有權重都不是負數。
鬆弛：發現一條更近的路
所有最短路徑演算法都建立在同一個動作上，叫做鬆弛（relaxation）。
dist[v] 是「目前知道的、從起點到 v 的最短距離」，一開始除了起點是 0，其他都是 ∞（還不知道怎麼到）。
現在有一條邊 u → v，權重 w。如果「先到 u，再走這條邊」比目前知道的還近，就更新：
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w # 找到更近的走法
parent[v] = u # 記下：最短路徑上，v 的前一站是 u
dist 只會越來越小，最後停在真正的最短距離。不同的演算法差在「按照什麼順序鬆弛哪些邊」：
- Dijkstra：每次挑「目前距離最小、還沒確定」的節點，鬆弛它的所有邊；每條邊只需要鬆弛一次
- Bellman-Ford（本課最後）：不挑順序，把所有邊一輪一輪地鬆弛，最多 V - 1 輪
Dijkstra：每次確定距離最小的那一個
Dijkstra 演算法的步驟：
dist[起點] = 0，其他都是 ∞- 在「還沒確定」的節點裡，挑
dist最小的節點 u，宣布 u 的最短距離確定了 - 鬆弛 u 的每一條邊
- 重複 2、3，直到所有走得到的節點都確定
為什麼第 2 步可以直接「確定」？因為所有權重都 ≥ 0：其他還沒確定的節點，距離都 ≥ dist[u]， 從它們繞過來只會更長（或一樣長），不可能讓 u 變得更近。
「挑最小的」要快，就用第 15 課的優先佇列（最小堆積）。佇列裡存 (距離, 節點)，先比距離，距離相同再比節點編號：
| 語言 | 寫法 |
|---|---|
| Python | heapq.heappush(pq, (d, v))、heapq.heappop(pq)：tuple 本來就是先比第一個、再比第二個 |
| C++ | priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>：預設是最大堆積，加 greater 變成最小堆積 |
| Java | PriorityQueue<int[]> 加比較器：a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]) |
一般的堆積不能「把某個節點的距離改小」，所以常見的做法是：距離變小時直接再放一筆新的進去，
舊的那筆留在裡面。之後取出舊紀錄時，發現那個節點已經確定過了，就丟掉它。下面的範例用 done 陣列判斷。
Dijkstra：優先佇列、dist、parent
注意節點 1：一開始從 0 直接過去是 4，後來從 2 繞過去只要 1 + 2 = 3，dist[1] 被改小，優先佇列裡同時有 (3, 1) 和 (4, 1) 兩筆。(3, 1) 先被取出，1 確定；之後取出 (4, 1) 時，1 已經確定過，這筆舊紀錄就被丟掉。節點 3、4 也各有一筆舊紀錄。
要花多少時間
每條邊最多讓優先佇列多一筆紀錄，所以佇列裡最多有 O(E) 筆；每次放進、取出都是 O(log E)。 所有邊都會被鬆弛一次，總共是 O((V + E) log V)（log E 和 log V 只差常數倍，因為 E 最多約 V²）。
| 演算法 | 適用 | 時間複雜度 |
|---|---|---|
| BFS | 沒有權重（或權重都相同） | O(V + E) |
| Dijkstra（優先佇列） | 權重都不是負數 | O((V + E) log V) |
| Bellman-Ford | 可以有負權重，還能偵測負環 | O(V × E) |
下面的實驗室可以自己改權重，看最短路徑怎麼跟著改變。
還原路徑，以及舊紀錄的另一種處理方式
和 BFS 一樣，parent[v] 記著最短路徑上 v 的前一站。從終點沿著 parent 往回走到起點，就得到整條路徑。
上一課是先收集再倒過來；這次示範另一種寫法：每走一步就插在串列最前面，收集完就是正確的順序
（插在前面每次要 O(n)，路徑不長時沒有關係）。
下面的範例也換了一種判斷舊紀錄的方式，不用 done 陣列：
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # 取出的距離比目前知道的還大：這筆是舊的
一個節點被確定時，取出的 d 一定等於 dist[u]；如果 d 比較大，表示放進這筆之後又找到了更短的路，這筆就沒用了。
兩種寫法的結果相同，在權重都不是負數時可以互換。
圖是幾個城市之間的示意行車時間（分鐘）。台北直接到新竹是 80 分鐘，但經過桃園只要 40 + 35 = 75 分鐘。
還原最短路徑：台北到台中
前半段是 Dijkstra（這次用 d > dist[u] 丟掉舊紀錄）；回到主程式後，從台中（4）沿著 parent 往回走，每一站都插在 path 的最前面。新竹到台中直接走要 100 分鐘，經過苗栗只要 40 + 45 = 85 分鐘。
想一想：Dijkstra 的步驟
下面的程式對一張有向圖執行 Dijkstra，會印出什麼？
import heapq
adj = [[(1, 6), (2, 2)], [(3, 1)], [(1, 3), (3, 7)], []]
dist = [10**9] * 4
dist[0] = 0
pq = [(0, 0)]
order = []
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
order.append(u)
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
print(order, dist)
優先佇列裡同時有 (4, 1) 和 (3, 1) 兩筆節點 1 的紀錄，這是怎麼來的？
Dijkstra 為什麼可以在節點被取出的那一刻，就宣布它的最短距離確定了？
負權重：Dijkstra 會算錯
權重有時候可以是負數，例如「這段路有補助，反而賺錢」、或是金融上的匯率套利。 這時 Dijkstra 的關鍵推論「取出時就確定」就不成立了。看這張有向圖：
0 → 1 權重 2
0 → 2 權重 5
2 → 1 權重 -4
1 → 3 權重 1
正確答案：0 到 1 最短是 0 → 2 → 1，5 - 4 = 1；0 到 3 最短是 0 → 2 → 1 → 3，1 + 1 = 2。
Dijkstra 會先確定 1（距離 2），接著用它更新 3（距離 3）並確定 3。等到處理 2 時，才發現經過 2 到 1 只要 1， 可是 1 和 3 都已經「確定」了，3 不會再被更新，最後印出錯的 3。
下面的範例用和前面相同的 Dijkstra 程式（用 done 陣列的寫法），看它在哪一步出錯。
負權重讓「已確定」的距離又變小
看輸出：確定的順序是 0、1、3、2，其中 3 在 2 之前就確定了，距離 3。處理 2 的時候，dist[1] 從 2 變成 1，但 1 早就確定過了，1 → 3 這條邊不會再被鬆弛，所以最後 0 到 3 印出 3，正確答案是 2。
Bellman-Ford：一輪一輪鬆弛所有的邊
有負權重時，可以改用 Bellman-Ford 演算法。名稱來自 Lester Ford Jr.（1956）和 Richard Bellman（1958）各自發表的方法， Edward F. Moore 在 1959 年也發表過類似的做法。
做法很直接：不挑順序，把每一條邊都鬆弛一次，這樣算一輪；做 V - 1 輪。
為什麼 V - 1 輪就夠？如果沒有負環，最短路徑最多經過 V 個節點、V - 1 條邊。 第 1 輪之後，「只用 1 條邊」的最短路徑一定已經算對；第 2 輪之後，「最多 2 條邊」的也算對……第 V - 1 輪之後，全部都對了。
負環（negative cycle）是權重總和為負的環：沿著它一直繞，距離可以無限變小，「最短距離」就沒有定義。 偵測方法是做完 V - 1 輪後再多檢查一輪：如果還有邊能讓距離變小，就表示有負環。
時間複雜度是 O(V × E)，比 Dijkstra 慢，所以只有在可能出現負權重時才用它。
Bellman-Ford：每一輪 dist 怎麼變
邊故意排成「從終點往起點」的順序，所以每一輪只能往前推進一條邊：第 1 輪算對了 1、2 的初步距離，第 2 輪才發現 0 → 2 → 1 更近，第 3 輪才把 3 更新成 2。最後多檢查一輪，沒有邊能再讓距離變小，表示沒有負環。
想一想：負權重與 Bellman-Ford
一張圖有 6 個節點、可能有負權重（但沒有負環）。Bellman-Ford 最多需要做幾輪，才保證所有 dist 都正確？
做完 V - 1 輪之後，再檢查一輪時發現 dist[u] + w < dist[v] 仍然成立，這代表什麼？
下面哪一種情況，適合用 Dijkstra？
實作：補上鬆弛
下面是一張 7 個節點的有向圖，Dijkstra 的骨架已經寫好，只缺迴圈裡的鬆弛。請補上：經過 u 到 v 比較近，就更新 dist[v] 並把新的紀錄放進優先佇列。節點 6 從 0 走不到，要印出「到不了」。
重點整理
- 有權重的圖裡，路徑長度是權重總和；「邊最少」不等於「最短」，BFS 不夠用
- 鬆弛：
dist[u] + w < dist[v]時更新dist[v]與parent[v]；最短路徑演算法的差別在鬆弛的順序 - Dijkstra（1959）每次從優先佇列取出距離最小、還沒確定的節點，宣布它確定，再鬆弛它的邊；O((V + E) log V)
- 優先佇列存
(距離, 節點)；距離變小時再放一筆，取出舊紀錄時用done[u]或d > dist[u]丟掉 - 沿著 parent 從終點往回走，就能還原最短路徑
- 有負權重時 Dijkstra 可能算錯；Bellman-Ford 把所有邊鬆弛 V - 1 輪，O(V × E)，多檢查一輪還能偵測負環
下一課：最小生成樹。不是找兩點之間的最短路，而是用總權重最小的一組邊把所有節點連起來；會用到 Kruskal 演算法與 Union-Find。