戴克斯特拉走到盡頭的地方
上一篇指南以一句警告作結：戴克斯特拉之所以快，正是因為它敢在某個頂點一被從優先佇列取出的當下就把它定案，從不回頭。這個賭注只有在所有邊權皆非負時才划得來，因為這樣一來，之後才發現的路徑永遠不可能更便宜。但只要存在一條負權邊，這個賭注就可能輸掉：一個被提早封閉的頂點，原本也許能透過一條稍後才下降一條負權邊的路徑、以更低的成本抵達，而戴克斯特拉早已掉頭走開了。所以我們需要一個不下這種賭注的方法——一個無論改善來得多晚，都願意持續更新估計值的方法。
我們需要的一切，在第 1 篇指南裡早已備齊。回想那個唯一的基本動作：鬆弛一條邊 (u, v)（權重為 w）問的是「先走到 u 再跨過這條邊，會比我目前對 v 的最佳猜測更便宜嗎？」——若 dist[u] + w < dist[v]，就把 dist[v] 降到 dist[u] + w，並記下 u 是 v 的前驅。鬆弛永遠是安全的：它絕不會把估計值壓到真正的最短距離之下；而真正的距離正是一個不動點，在那裡任何邊都再也無法被鬆弛。戴克斯特拉只是鬆弛的一種有紀律的排程。貝爾曼-福特採取相反的姿態——它徹底放棄了對順序耍聰明。
就把每條邊鬆弛 V-1 次
整個演算法就在這裡。設 dist[source] = 0，其餘每個 dist 設為無限大。接著做一次遍歷：把全部 E 條邊，以你喜歡的任一固定順序走過一遍，逐一鬆弛。然後再做一次完整遍歷。再做一次。貝爾曼-福特演算法恰好跑 V-1 次這樣的遍歷（V 是頂點數），然後停止。就這樣——沒有優先佇列、沒有已訪集合、不用決定下一個該處理哪個頂點。笨拙、近乎無腦的重複。
for i in 1 .. V-1: # V-1 passes
for each edge (u, v, w): # all E edges, any order
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pred[v] = u為什麼是 V-1，又為什麼這樣就夠了？來自第 1 篇指南的關鍵事實是：在沒有負環的圖裡，最短路徑永遠不需要重複經過任一頂點，因此最多用 V-1 條邊。現在來看完整遍歷的魔法：第 1 次遍歷後，凡是最短路徑長度為 1 條邊的頂點，其 dist 都已正確；第 2 次遍歷後，凡是可由 2 條邊的最短路徑抵達的頂點都正確；一般而言，第 k 次遍歷後，凡是最短路徑最多用 k 條邊的頂點，其 dist 都正確。既然沒有最短路徑超過 V-1 條邊，V-1 次遍歷後每個距離都已塵埃落定。這個證明是對 k 做一次乾淨的數學歸納法——下一段正是這個論證。
- 基底情形（k = 0）：在任何遍歷之前，dist[source] = 0 是正確的——它是唯一最短路徑用 0 條邊的頂點。
- 歸納步驟：假設第 k-1 次遍歷後，凡最短路徑最多用 k-1 條邊的頂點都已得到正確距離。取一個最短路徑恰好用 k 條邊的頂點 v，設它的最後一條邊為 (u, v)。
- 那麼 u 有一條 k-1 條邊的最短路徑，所以 dist[u] 早已正確。第 k 次遍歷會鬆弛每一條邊，包括 (u, v)，於是把 dist[v] 設成 dist[u] + w——也就是真正的最短距離。
- 由歸納法，V-1 次遍歷後所有距離都正確，因為沒有最短路徑長過 V-1 條邊。
負環究竟意味著什麼
留意那個證明重重依賴的一句話：「最短路徑永不重複經過頂點。」這只有在沒有負環時才成立——負環是指一個環，其邊權總和為負數。若這樣的環存在、可從源點抵達、又能通往你的目標，那麼「最短路徑」就不再是一個有良好定義的東西。每繞這個環一圈，你就再減去一些權重，於是成本可以無止境地往下壓。沒有最短路徑，只有一場朝著負無限大的無盡下墜。這不是一個待修補的臭蟲——它是輸入本身一個真實的特性，任何誠實的最短路徑方法都必須回報它，而非吐回一個毫無意義的數字。
而這絕非什麼奇異的邊界案例。只要邊所建模的是收益與損失、而非物理距離，負權就會冒出來——外匯套利（某個交易迴圈走完後，錢有沒有比一開始更多？）、利潤與成本構成的網路，或是一些約束系統，其中的矛盾恰恰以一個負環的形式浮現。問「有沒有負環？」往往就是整個計算的重點本身，而不是要閃避的角落情況。戴克斯特拉連這個問題都問不出口。貝爾曼-福特卻幾乎免費地回答了它。
第 V 次遍歷：一台免費的測謊機
這裡是優雅的部分。我們證明了：在沒有負環時，所有距離在 V-1 次遍歷後就已定案——意思是此刻沒有任何邊還能被鬆弛；系統已抵達它的不動點。所以再多跑一次，第 V 次。如果在這次額外遍歷中還有某條邊 (u, v) 仍能鬆弛——也就是 dist[u] + w < dist[v] 依然成立——那麼就有一個距離，在它本該被凍結之後，又掉了下去。唯一能讓估計值永遠繼續往下壓的東西，就是負環。於是偵測它的規則簡單到極點：第 V 次遍歷上任何一次成功的鬆弛，就證明了存在一個可達的負環。
如果你想真正展示出那個作怪的環、而不只是知道它存在，前驅指標就能辦到。當第 V 次遍歷在某頂點 v 上發生鬆弛時，那個 v 可從某個負環抵達。沿著 pred[] 往回走 V 步，以確保你已踏上環本身，接著繼續跟著 pred[] 走，直到回到一個已經見過的頂點——兩次造訪之間的那些頂點，就拼出了這個環。這跟正常情況下用來重建最短路徑本身的，是同一條前驅鏈；只是在這裡，它重建的是「無解」這件事的證明。
代價，以及種種連結
誠實地數一下工作量：V-1 次遍歷（外加一次偵測遍歷），每次都碰全部 E 條邊，總共是 O(V*E)。在 E 約為 V^2 的稠密圖上，這是 O(V^3)——明顯慢於戴克斯特拉的 O(E + V log V)。這就是你買下的交易：貝爾曼-福特付出一筆實實在在的漸進溢價，換來處理負權邊、並為其負環開立證明的能力。一如既往，大O符號藏起了常數與小輸入的行為——在極小的圖上，這個簡單的雙重迴圈也許勝過戴克斯特拉堆積的額外開銷——但論及擴展，當權重非負時戴克斯特拉決定性地勝出。在你非用不可時才用貝爾曼-福特，而不是預設就用。
有兩個實用的改良值得知道，但要附上誠實的但書。第一，提早終止：若某一整次遍歷沒有鬆弛任何邊，不動點便已抵達，你可以立刻停下——往往遠在 V-1 次遍歷之前。這在典型輸入上幫助極大，卻不改變最壞情況的 O(V*E)；對手能逼出全部 V-1 次遍歷。第二，以佇列為基礎的變體（常稱 SPFA）只重新檢視「距離剛剛改變的頂點」所引出的邊，實務上通常快得多——然而它的最壞情況仍是 O(V*E)，在精心構造的圖上完全沒有漸進上的改善。平均更快不等於最壞情況更快；請把這兩者分清楚。
最後，看看它在更大的故事裡的位置。貝爾曼-福特是單源最短路徑在負權下的主力，它也是更廣處的關鍵基石。在下一篇指南裡，當我們攻打帶負權邊之圖上的全點對問題時，強生演算法會恰好跑一次貝爾曼-福特——主要目的不是求距離，而是算出一套巧妙的重新賦權，把每條邊都變成非負，之後便能從每個頂點放出快速的戴克斯特拉。貝爾曼-福特肯與負性周旋的這份意願，正是那個技巧得以成立的許可證。緩慢、簡單、又誠實，它是那把拒絕別過頭去、敢於正視戴克斯特拉無法面對之情況的工具。