一個動作，眾多演算法
在圖搜尋那一階，你靠數邊來走一張圖：廣度優先搜尋找到跳數最少的路線，因為每一步成本都相同。現在我們加上權重——每條邊上的一段距離、一筆過路費、一段行車時間——並改問最便宜的路線，這裡「最便宜」指的是總權重最小，而非邊數最少。三段各為 1 的繞路勝過一條權重 10 的沉重邊。這就是單源最短路徑問題：從一個源點出發，一次找出到其他每個頂點最低成本的路線。這一整階了不起的地方在於，解它的每個演算法——戴克斯特拉、貝爾曼-福特、DAG 掃描——都由同一個操作以巧妙的順序反覆執行而成。
那個操作就是邊鬆弛，而它小得近乎令人不好意思。維護一個陣列 d，d[v] 是你目前對「從源點到 v 的距離」最好的猜測。看著一條從 u 到 v、權重為 w 的單一邊，問一個問題：「若我走到 u 再走這條邊，會不會比我目前對 v 的猜測更便宜？」若 d[u] + w 小於 d[v]，就把 d[v] 調低到 d[u] + w。整個動作就這樣——一次比較，也許一次賦值。鬆弛一條邊只能調低估計值、絕不調高，而一條已經好到不能再好的邊，只會讓 d 原封不動。這一階的一切，都是「該鬆弛哪些邊、以什麼順序」這個問題的變奏。
relax(u, v, w): # try the shortcut: source -> ... -> u -> v
if d[u] + w < d[v]:
d[v] = d[u] + w # found a cheaper known path to v
pred[v] = u # remember the road we came in on為何鬆弛永遠安全
在操心順序之前，先安頓一個更基本的擔憂：鬆弛會不會把事情弄錯？這裡有那個承重的不變量，正是你在正確性那一階證過的那種迴圈不變量。在每一刻，d[v] 都是從源點到 v 某條真實路徑的長度（若你還沒找到任何路徑則為無限大）。它絕不是憑空的數字——它總是由你已經發現的某條實際路線所達成。因此 d[v] 永遠是高估：它可以等於真正的最短距離，卻絕不會跌到它之下，因為沒有路徑比最短的那條更短。
- 初始化：令 d[源點] = 0（空路徑，長度 0），其餘 d[v] = 無限大。不變量成立——0 是某條真實路徑的長度，而無限大誠實地說「尚未找到路徑」。
- 維持：當 relax(u, v, w) 觸發時，新的 d[v] = d[u] + w 是（一條到 u 的真實路徑）接上（邊 u->v）的長度——本身就是一條到 v 的真實路徑。所以不變量在每次鬆弛後都存活。
- 推論：因為 d[v] 始終是某條真實路徑的長度，所以無論何時都有 d[v] >= dist(v)。鬆弛只能把 d[v] 往 dist(v) 推近，絕不會越過它——所以多餘的、順序錯亂的鬆弛只是白費功夫，絕非錯誤。
這是一個極其寬容的情形。你不會因為鬆弛了不需要鬆弛的邊、或以愚蠢的順序鬆弛它們而破壞正確性——最糟也不過是做了無用功。這份自由，正是為什麼這麼多不同的演算法能共用同一具引擎：它們全都收斂到同一個正確答案，而彼此競爭的只是「需要多少次鬆弛才能抵達那裡」。正確性是免費的；效率才是整場較量。
何時算做完？三角不等式
若鬆弛絕不會超調，那麼出錯的唯一可能就是停得太早——在某個 d[v] 仍大於 dist(v) 時就收手。所以你需要一個停止測試。它來自一個純粹的常識，叫做三角不等式：繞路絕不會更划算。對每條權重為 w 的邊 (u, v)，真正的距離滿足 dist(v) <= dist(u) + w。為什麼？右邊是到 v 某條特定路線的成本——先走到 u 的最佳路線，再走那條到 v 的單邊——而 dist(v) 是所有路線中的最小值，所以它不可能超過其中任何一條。
現在把它翻譯成對你估計值的測試。一條邊 (u, v) 可被鬆弛，恰恰當 d[u] + w < d[v]——也就是恰恰當 d 在那條邊上違反三角不等式時。所以「沒有任何邊還能被鬆弛」與「d 處處滿足三角不等式」是同一句話。而有一條定理：一旦對每個可達的 v 而言 d[v] 都是有限的、且沒有任何邊可被鬆弛，則對所有 v 都有 d[v] = dist(v)。一條可鬆弛的邊是一個你看得見、修得了的瑕疵；當再無瑕疵時，估計值已無處可降，而一個無處可降的高估值，必然早已精確。這個單一的等價——可鬆弛的邊等於被違反的三角不等式——正是這一階每個演算法底下的收斂測試。
一個你能徒手做的小推演
取四個頂點 s、a、b、t，邊為 s->a (4)、s->b (1)、b->a (2)、a->t (3)、b->t (7)。從 d[s] = 0、其餘無限大開始。鬆弛 s 的邊：d[a] 變為 4，d[b] 變為 1。現在鬆弛 b 的邊：b->a 試 1 + 2 = 3，勝過目前的 4，故 d[a] 降到 3（且 pred[a] 變為 b）；b->t 試 1 + 7 = 8，故 d[t] 變為 8。最後鬆弛 a 的邊 a->t：3 + 3 = 6 勝過 8，故 d[t] 降到 6，pred[t] = a。
檢查停止測試：還有任何邊可被鬆弛嗎？d[a] = 3 是經由 b 而來，而 0 + 4 = 4 不小於 3，故 s->a 沒問題；其他每條邊同樣滿足 d[u] + w >= d[v]。沒有邊違反三角不等式，所以我們做完了，答案是最終值：dist(a) = 3、dist(b) = 1、dist(t) = 6。注意到 a 最便宜的走法是兩段的路線 s->b->a（成本 3），而非權重 4 的直接邊——「最短」真的指的是總權重最小。也注意到順序對速度有影響：若在 b 的邊之前鬆弛 a 的邊，會先用過時的 d[a] = 4 去設定 d[t]，然後得再修一次。不同的順序，相同的最終答案。
順序就是一切——還免費附贈一棵樹
既然正確性是自動的，設計問題就化簡為一個問題：哪一種鬆弛順序，能以最少的功夫抵達「無邊可鬆弛」的狀態？正是這個單一問題，把這一階分裂成各個演算法。粗暴的答案是貝爾曼-福特：就把每條邊一遍又一遍地鬆弛 V-1 次——以 O(V*E) 而言慢，但它不會漏掉，甚至能在負權重下存活。而當所有權重非負時，巧妙的答案是戴克斯特拉演算法：總是接著定案最近的未完成頂點，這讓每條邊恰好只鬆弛一次。在一張有向無環圖上，按拓樸排序鬆弛則在單次線性掃描中完成。同一個原子、三種順序、三種執行時間。
「至少把最短路徑上的每條邊以正確的次序各鬆弛一次」之所以無人能超越，是有原因的。最短路徑具有最佳子結構：最短路徑的任一子路徑本身也是最短的。若到 t 最便宜的路線經過 a，那麼那條路線中從源點到 a 的那一段，本身必定也是到 a 最便宜的路線——否則你大可換上一段更便宜的、勝過那條號稱最佳的到 t 路線，矛盾。這正是動態規劃背後同一個最佳子結構構想，也是為什麼按正確順序鬆弛各邊根本行得通：每個正確的距離，都由一個較小的正確距離加上最後一條邊建成。
最後一份禮物，從我們一直默默記錄的 pred 指標中掉了出來。每當一次鬆弛調低了 d[v]，我們就設 pred[v] = u——我們抵達時所走的那條路。最後，那些前驅邊串接成一棵以源點為根的最短路徑樹：從任一頂點沿 pred 走回 s、再反轉，你就得到一條實際最便宜的路線，而不只是它的成本。GPS 需要的是路線、而不只是里程，而這棵樹一次交付每一條路線，因為最佳子結構讓共享的前綴成為共享的分支。（別把它與第 5 篇指南的主題最小生成樹混淆——那一棵最小化邊權總和、且根本沒有源點；兩棵樹解決不同的問題、通常也長得不一樣。）有了鬆弛、不變量、三角不等式停止測試，以及這棵樹在手，你已準備好去認識各個具體演算法——從戴克斯特拉開始，以及它為何連一條負邊都容不下。