從有耐心的鬆弛，到一個貪婪的順序
前一篇留給我們一個操作，鬆弛，以及一個承諾：只要以正確的順序鬆弛邊，每個暫定距離最終都會收斂到從源點出發的真正最短距離。麻煩就在「正確的順序」這幾個字。下一篇要講的貝爾曼-福特演算法乾脆放棄聰明，把每條邊一遍又一遍地鬆弛，代價是 O(V·E)。戴克斯特拉的問題更銳利：我們能不能找到一個好到讓每條邊只鬆弛一次、永遠不必回頭的順序？
戴克斯特拉的答案是一個貪婪的排序。維持兩群頂點：已定案的，其最短距離我們已經鎖定；以及邊界的，它們仍帶著一個可能還會變好的暫定距離。每一步，看遍所有尚未定案的頂點，挑出暫定距離最小的那一個，把它宣告為已定案。接著鬆弛它的出邊，以便可能調低鄰居的暫定值，然後重複。整個演算法就只是這個迴圈：挑最近的、鎖定它、向外鬆弛。
一段小小的追蹤
讓我們在四個頂點上用手跑一遍。源點 s，邊有 s→a 權重 1、s→b 權重 4、a→b 權重 2、a→c 權重 5、b→c 權重 1。起始：除了 dist(s) = 0，每個距離都是無限大。邊界是 {s, a, b, c}，暫定值為 0、∞、∞、∞。挑出最小的——s，值為 0——把它定案，並鬆弛它的邊：a 降到 1，b 降到 4。
- 已定案 {s}。邊界暫定值：a=1、b=4、c=∞。最小的是 a=1，於是把 a 定案。鬆弛 a 的邊：經 a 到 b 是 1+2 = 3，勝過 4，所以 b 降到 3；經 a 到 c 是 1+5 = 6，所以 c 降到 6。
- 已定案 {s, a}。邊界：b=3、c=6。最小的是 b=3，於是把 b 定案。鬆弛 b 的邊：經 b 到 c 是 3+1 = 4，勝過 6，所以 c 降到 4。
- 已定案 {s, a, b}。邊界：c=4。把 c 以 4 定案。沒有東西可再鬆弛了。完成——最終距離為 s=0、a=1、b=3、c=4。
盯著我們把 b 以 3 定案的那一刻看。當時周圍還有尚未定案的頂點（c 為 6），但我們對 b 做了承諾，而且再也不回頭看。那個承諾正是戴克斯特拉速度的來源——也正是我們現在必須證成的賭注。當還有更多鬆弛在後頭時，我們憑什麼相信 3 就是 b 的最終答案？
為何這個賭注是安全的——當權重非負時
要捍衛的主張是貪婪選擇性質：在我們挑出暫定距離最小的邊界頂點 u 的那一刻，那個暫定距離就已經等於 u 的真正最短距離。若此成立，把 u 定案就絕不會太早，而一趟就足夠。這個證明是一個小而優美的論證——一種保持領先風格的反證，整個關鍵就在邊永遠不會有負權重。
為了反證，假設在我們挑出 u 的那一刻，u 的真正最短距離嚴格小於它的暫定距離 d(u)。那麼存在某條確實更短的路徑 P 抵達 u。沿著 P 從源點走；既然源點已定案而 u 尚未，P 必定在某條邊 (x, y) 上從已定案集合跨到邊界，其中 x 已定案、而 y 是 P 上第一個邊界頂點。因為 x 較早就以正確距離被定案，且我們在定案 x 時鬆弛了它的邊，y 此刻已有一個至多為 dist(x) + weight(x,y) 的暫定值——也就是 P 走到 y 為止的長度。
現在是關鍵句。P 走到 y 為止的長度，至多等於整條 P 的長度（因為 P 剩下的部分，從 y 往後到 u，長度 ≥ 0——這就是用到非負性的地方）。而整條 P 依假設又比 d(u) 短。所以 y 的暫定值小於 d(u)。但這與我們把 u 挑為最小邊界頂點相矛盾——y 當時就坐在邊界裡，帶著一個更小的值。這個矛盾意味著不存在這樣更短的路徑：d(u) 自始至終都是對的。
一條負邊，房子就垮了
讓我們親眼看著失敗發生，因為沒有什麼比一個你親手追蹤過的反例更能建立直覺。三個頂點，源點 s，邊有 s→a 權重 1、s→b 權重 2、以及 b→a 權重 -2（一條負邊）。到 a 的真正最短距離是經由 b：2 + (-2) = 0，勝過直達的 1。但看看戴克斯特拉怎麼做。
- 把 s 以 0 定案。鬆弛：a 降到 1，b 降到 2。邊界：a=1、b=2。
- 最小的邊界頂點是 a，值為 1，於是把 a 以 1 定案——並永遠鎖死。這就是致命的一步：a 在 b 還沒被處理之前就被定案了。
- 現在把 b 以 2 定案並鬆弛 b→a：2 + (-2) = 0，小於 a 儲存的 1。但 a 早已定案；標準演算法絕不會回頭看它。戴克斯特拉回報 dist(a) = 1。真正的答案是 0。它就是錯了。
這正是我們的證明所禁止的情況。貪婪論證假設：一旦你抵達某個頂點，未來的繞路都不可能讓它更便宜，因為每條剩下的邊都加上某個非負的東西。一條負邊打破了那個假設：一條看起來更長、經過 b 的路線，在前往 a 的途中減去了東西，所以提早把 a 定案——當它還看起來是最好的時候——是一個演算法沒有任何機制能撤銷的錯誤。這個錯誤不是任何實作中的程式臭蟲；它是烤進貪婪策略本身裡的。
讓它變快：優先佇列
正確性搞定了，那戴克斯特拉的成本是多少？最貴的部分是「找出暫定距離最小的邊界頂點」——要做 V 次。每次都天真地掃過所有頂點，得到 O(V^2)，對於 E 接近 V^2 的稠密圖來說，這其實很好、甚至是最佳的。但對稀疏圖我們想要更好的，而工具是一個最小優先佇列（二元堆積）：它能在 O(log V) 內交出最小的暫定值，並支援在鬆弛改善某個鄰居時調低一個鍵。
數一數堆積操作。每個頂點被取出一次（V 次 extract-min 操作），而每條邊至多觸發一次 decrease-key（共 E 次）。每個堆積操作是 O(log V)，得到 O((V + E) log V)，通常寫成 O(E log V)，因為在連通圖上 E ≥ V。那就是你該記下的執行時間。用更花俏的費氏堆積，decrease-key 變成攤還 O(1)，界限改善為 O(E + V log V)——一個在實務上很少勝過樸素二元堆積的理論勝利，小小提醒了我們隱藏常數是有影響的。
dist[s] = 0; all other dist = +inf
push (0, s) into min-heap PQ
while PQ not empty:
(d, u) = extract-min(PQ)
if d > dist[u]: continue # stale entry, skip
for each edge (u, v, w):
if dist[u] + w < dist[v]: # relaxation
dist[v] = dist[u] + w
push (dist[v], v) into PQ你帶走的東西
在整道階梯裡，戴克斯特拉是關於「貪婪選擇如何掙得它的地位」最乾淨的案例研究——也是關於「掙得地位的條件可以多麼狹窄」的案例研究。同一個迴圈，在非負權重上可被證明為最佳，遇上一條負邊卻可被證明為錯誤，而再小心的程式碼都救不了它；只有換一個範式才行。當你要動用戴克斯特拉時，第一個問題從來不是「圖大不大？」，而是「所有權重都非負嗎？」——而前一篇的三角不等式，正是這裡的正確性與那裡的失敗底下都藏著的那個安靜事實。
它也留給你一個可移植的習慣。每當有人提出一個貪婪演算法，就照我們做的去做：找出它正確性證明裡那唯一一行依賴於對輸入之假設的句子，然後問：拿掉那個假設時，什麼會壞掉。對戴克斯特拉來說那一行是「剩餘路徑長度 ≥ 0」。知道一個證明往哪裡傾斜，就是精準知道一個演算法何時可被信任——這正是建出一棵你真能依靠的最短路徑樹的全部意義。