負權邊可能帶來較短路線
假設邊的權重記錄成本變化,其中包括回贈或退款。負權邊可以有實際意義,卻也改變了最短路徑算法必須證明的事情。目前看似昂貴的路線,可能在之後經過負權邊,改善某個看似已確定的距離。Dijkstra 算法所用的貪心定案步驟,便失去原有理據。
Bellman–Ford 依靠另一種推進方式:容許路線使用更多邊,並把已知路線延長一條邊,反覆改善距離估計。關鍵問題是:最優解存在時,為何有限輪次就足夠?若之後仍能改善,又能推知甚麼?
本節由動態規劃及不變量分析出發,發展最短路徑算法。我們會分清兩種計算:遞歸表格的輪次有明確意義;原地更新實作的一輪,卻可能已沿多條邊傳播改善。
釐清圖問題與例外情況
設 是有限有向圖,,來源為 ,每條邊有實權重 。平行邊可保留為不同的邊記錄,也容許自環。數學分析中的運算及比較皆為精確。
遊走是端點相接的有向邊序列,可以重複頂點或邊,其權重為所經各邊權重之和。由 到自己的空遊走,權重為零。簡單路徑不重複頂點,因此至多有 條邊。
定義 7.1.1
(最短遊走距離)
對 ,以 表示全部由 到 的遊走權重之下確界,有三種可能:
- :由 不能到達 ;
- 有限最小值:存在一條最優遊走;
- :到 的遊走權重可以任意小。
負環是總權重為負的有向環。若由 可到達某負環,而且由該環可到達 ,便可先反覆繞環再前往 ,證明 。
可達條件不可省略。圖中另一部分的負環,不影響由 出發的路線。即使負環可達,也不是每個頂點的距離都變成 :只有由該環能到達的頂點才受影響。下方算法回報的是:是否有某個負環可由 到達;它本身不會把所有距離為 的頂點分類。
先限制遊走的邊數
對整數 ,定義 為由 到 、使用至多 條邊的遊走之最小權重;若沒有這種遊走則設為 。固定有限的 後,這類遊走只有有限多條,所以即使圖有負環,有限最小值仍存在。
初始值為
至多使用 條邊的遊走,要麼本來已使用至多 條,要麼最後一條邊是 ,之前至多有 條邊。因此
若前一個值為 ,便略過該候選。沒有任何入邊候選時,內層最小值設為 。保留第一項十分重要:邊數是「至多」,不是「恰好」。
命題 7.1.2
(邊數上限遞推式)
對每個 及每個 ,上面定義的 都滿足該遞推式,而右方只需由第 行計算。
證明
(按最後一條邊分解)
設 為右方的值。至多使用 條邊的遊走,要麼至多使用 條邊,其權重至少為 ;要麼以某條 結束,之前的起始部分至多有 條邊。起始部分的權重至少為 ,所以整條遊走的權重至少為候選值 。因此 ;若 ,便沒有合規遊走。
反過來, 的每個有限項都是某條合規遊走的權重: 由至多 條邊的遊走取得,有限候選則由一條至多用 條邊到 的最優遊走接上 取得。因此 ,兩者相等;由所訂的第 行出發,對 歸納,便證明整張表正確。
完整表格說明為何需要多輪
使用頂點 ,邊如下;除此以外沒有其他邊。
| 邊 | 權重 | 邊 | 權重 |
|---|---|---|---|
例題 7.1.3
(到 t 的最佳路線使用四條邊)
每一行只能用前一行計算:
| 邊數上限 | |||||
|---|---|---|---|---|---|
例如 。在邊數上限二的一行,由 延長路線時尚不能使用新值 2,因為每一格都只能讀取第一行,所以 。上限三才得到 及 ;上限四最後得到 ,由以下路徑取得:
若同一行內使用剛寫入的值,計算描述的是原地掃描,而非這張邊數表。這仍可能形成正確算法,但該行便不再具有所訂的精確意義。
沒有可達負環時,為何 n − 1 輪足夠
定理 7.1.4
(沒有可達負環時邊數已經足夠)
若由 不能到達任何負環,則對每個 都有 。
證明
(縮短重複頂點的遊走)
假設由 不能到達任何負環。若由 出發的遊走重複某個頂點,兩次出現之間構成閉遊走。它可分解為有向環;按假設,每個環的權重均非負。移除這一段不會增加總權重。反覆移除,直到沒有重複頂點。
因此,每個可達的 都存在最優簡單路徑。簡單路徑只有有限多條,每條至多有 條邊,所以對每個 都有
不可達頂點的兩邊均為 。對 ,空路徑仍以零權重最優。此論證不要求每條邊非負,而是要求不存在可達的負環。
用適當不變量證明原地鬆弛
一條邊的鬆弛,是嘗試候選值 d[u] + w(u,v),只有它較小時才取代 d[v]。一般實作只儲存一個距離陣列,反覆掃描全部邊。
BELLMAN_FORD(V, E, s):
d[v] = INFINITY for every vertex v
d[s] = 0
repeat n - 1 times:
changed = false
for each edge (u, v, weight) in E:
if d[u] is not INFINITY and d[u] + weight < d[v]:
d[v] = d[u] + weight
changed = true
if not changed:
return (d, no reachable negative cycle)
for each edge (u, v, weight) in E:
if d[u] is not INFINITY and d[u] + weight < d[v]:
return (no distance answer, reachable negative cycle)
return (d, no reachable negative cycle)
INFINITY 表示獨立的不可達狀態,不是可以放心加上權重的最大整數。固定寬度整數實作必須先檢查此狀態,並確保每個有限和都能由所選型別表示。本節證明使用精確運算;浮點數的捨入可能改變嚴格比較的結果。
與表格不同,原地掃描可以立即使用剛改善的值。若按一條路徑的前進方向掃描,一輪就可能把改善傳到終點。我們不聲稱其標籤等於相應的 行。
定理 7.1.5
(原地算法的精確性)
若由 不能到達任何負環,則算法返回時(經 輪,或在較早一輪沒有任何改動時)所持有的標籤 d[v],對每個 都等於 ;不可達的 則為 。
證明
(用兩個不等式夾出原地算法的答案)
第一,每個有限標籤 d[v] 都是某條由 到 的實際遊走之權重。初始的零標籤符合此性質;鬆弛時,把取得 d[u] 的遊走接上該邊,便保持此性質。因此沒有可達負環時,。
第二,完成 次整輪邊掃描後,。尚未掃描時成立。在下一輪中,標籤只會下降,所以處理 時,當時的 d[u] 不大於該輪開始時的值,而歸納假設使後者不大於 。全部邊處理完畢後,每個最後一條邊的候選及原有標籤都已考慮,遞推式因此給出 。
沒有可達負環時,完成 輪後,
所以標籤精確。不可達頂點不可能取得有限標籤,因為每個有限標籤都有實際遊走作證。即使存在負環,第二個不等式仍有用;需要小心的是第一個不等式所用的有限最優值解釋。
證明透視
兩個不同事實夾出答案
證明是一個夾逼,兩邊用到不同的事實。下界 只來自實際作證的遊走,對環沒有任何假設。上界 來自標籤只會下降,所以原地掃描即使不能逐行重現邊數表,也至少做得一樣好。兩邊靠前面的等式 相接,而「沒有可達負環」的假設正是在此處進入。
不明顯的一步是與邊數表比較,而不是分析掃描次序,所以邊的次序完全無關。欠缺該假設時夾逼便鬆開: 可以是 ,而 卻是有限數,標籤便不能被確認。下面的偵測掃描處理這種情況。
若整輪沒有任何改動,每條鬆弛不等式便已成立。下一輪由同一組標籤開始,會做完全相同的事,也不會改動。因此提早停止與繼續掃描的結果相同。它也不會掩蓋可達負環,下一個論證會說明原因。
例題 7.1.6
(提早停止的一次原地運行)
在五頂點圖上運行算法,按表中的邊次序掃描:、、、、、、、。對 ,初始為 。
第一輪中, 令 , 令 。接著 給出 ,故 。然後 令 ,而 提供 ,並不較小。再由 令 , 提供 , 提供 。一輪後 ,已等於第 行。
第二輪中每個候選都不小於當前標籤: 提供 , 提供 , 提供 。沒有任何改動,所以算法在至多 輪中只做了兩輪便返回。第一輪把改善傳過四條邊,因為邊的次序跟隨路徑;邊數表的一行做不到這一點。
額外一次改善可偵測可達負環
完成 輪後,再檢查每條邊一次,但不改標籤。若有限的 d[u] 仍能改善 d[v],便回報有可達負環;不要把當前數值當作最短距離返回。
定理 7.1.7
(負環偵測)
設主迴圈已結束,不論是經 輪,還是在某一輪沒有任何改動時。則存在邊 ,其 d[u] 有限且滿足 ,當且僅當由 可到達某個負環。特別地,有可達負環時不會出現整輪不變。
證明
(精確標籤與沿環加總)
若沒有可達負環,前面的定理已使標籤精確。把到 的最優遊走接上 ,得到一條到 的可行遊走,所以 ,任何邊都不能嚴格改善終點。因此一旦發現改善,原假設便不成立。
反過來,假設有可達負環。由 到環上每個頂點都有一條簡單路徑,因此經 輪後,其標籤均有限。若環上沒有任何邊可鬆弛,每條邊均滿足 。沿環相加,所有距離標籤抵消,得到 ,與負權重矛盾。因此至少一條邊仍可鬆弛。
同樣的加總也排除「有可達負環卻出現整輪不變」:所有鬆弛不等式保持不變,會沿路徑把由 出發的有限可達性傳下去,之後便與負環矛盾。
證明透視
兩個方向,兩種引擎
兩個方向並不對稱。「沒有環,所以沒有改善」依靠標籤的精確性,也就是依靠前面整個定理;它只多用到「延長遊走仍得遊走」這一點。「有環,所以有改善」除了環上標籤有限之外,完全沒有用到算法的任何性質。
後者的關鍵一步是抵消:若環上每條邊都滿足鬆弛不等式,沿環相加時每個標籤都以正負號各出現一次,留下 。逐條邊成立的條件,經不起負的總和。有限性來自至多 條邊的簡單路徑,這就是 輪足夠的原因。若環不可達,其標籤保持 ,有限前驅檢查會略過其邊,加總便無從形成;這就是不可達的負環不會被回報的原因。
例題 7.1.8
(負環影響部分距離,不是全部距離)
在五頂點圖中加上權重為 的 。環 的權重為 ,由 可達,且環上頂點可到達 。因此 的距離均為 。由於沒有邊返回 ,來源的距離仍是零。偵測回報有可達負環,但不會把每個項目改成 。
另一情況是保留原圖不變,新增一個分離分量,包含權重為 的 及權重為 的 。這個環為負,但由 不可達。兩個標籤維持 ,有限前驅檢查會略過這些邊候選。原分量的距離仍與完整表格相同。
負權邊使 Dijkstra 的貪心證明失效
反例模式
已定案的距離之後仍可能需要改善
取頂點 ,只有以下邊: 權重為 , 為 , 為 , 為 , 為 。
永久確定最小暫定標籤的 Dijkstra 實作,會先把 以 2 定案,再把 以 4 定案,之後才處理標籤為 5 的 。但 的權重為 。這個圖根本沒有有向環,因此問題來自負權邊,不是負環。容許已定案頂點重新開啟,會改變算法,通常的 Dijkstra 正確性與時間分析便不能直接沿用。
執行時間與返回結果的保證
命題 7.1.9
(算法的成本)
設 。算法最壞時間為 ,除輸入圖外,輔助的距離儲存量為 。
證明
(計算邊的檢查次數)
初始化花費 。至多 次主要掃描及一次偵測掃描,各檢查 筆邊記錄,每筆為常數時間,合共 。距離陣列有 項。
圖至少有一條邊時,常簡寫為 ;但 時,仍須計初始化的 。若保留邊數表的所有行,則需 距離儲存量;原地算法不需要該表。
實作要麼返回正確來源距離,要麼警告存在某個可達負環。環的具體證據、重建最短路徑,以及列出全部距離為 的頂點,都是需要額外記錄的輸出。尤其若要分類受影響頂點,可從主要掃描後仍可鬆弛之邊的終點開始,遍歷所有由它們可達的頂點。這是額外分類步驟,不能單憑每個當前有限標籤完成。
常見錯誤
常見錯誤
(把「至多」改成「恰好」)
若把 定義為恰好使用 條邊的遊走之最小權重,遞推式便失去第一項。只有一條權重為 的邊 時,,因為不存在恰好兩條邊的遊走,但 。「至多 條」的上限讓較短的遊走仍然可用。
常見錯誤
(用大整數代替 INFINITY)
假設不可達頂點的標籤為 ,而權重為 的邊 連接兩個不可達頂點。檢查 成立,於是 得到一個虛假的有限標籤。若 的權重為 ,標籤便不斷改變。偽程式碼中的有限前驅檢查正是為了防止這種情況。
常見錯誤
(偵測失敗後仍返回標籤)
取邊 權重 、 權重 、 權重 ,按此次序掃描,。兩輪後對 有 ,第三輪會令兩者都變成 。偵測測試發現 可鬆弛。這些有限標籤不是距離:真值是 ,算法必須回報負環。
有解練習
快速檢查
(計算邊數表時,不使用新的一行)
取頂點 ,邊為 權重 、 權重 、 權重 、 權重 。按頂點順序 求 各行,並給出一條到 的最優路線。
解答 · 答案
各行為 、 及 。邊數上限二時,尚不能把 的新值延伸到 ;6 來自前一行的 4。上限三時, 給出 。圖中沒有環,且三等於 ,所以最後一行已是真正距離。
快速檢查
(邊次序改變一輪內的傳播)
在路徑 上,三條邊權重均為 1,由初始距離陣列開始。比較按前進次序及反向次序做一次原地邊掃描的結果。它們會否與邊數遞推式矛盾?
解答 · 答案
按 次序,前進掃描得到 ,因為每個新值立即重用。反向掃描先遇到兩條起點不可達的邊並略過,最後才處理 ,得到 ,這剛好等於 。兩者都不與遞推式矛盾:原地證明只要求一輪後 ,且每個有限標籤有實際遊走作證。前進掃描的結果在 和 處小於 ,這是容許的;此處它等於 。
快速檢查
(可達性決定哪個負環有影響)
只有以下邊: 權重 2、 權重 、 權重 1、 權重 7、 權重 、 權重 1。由 出發,哪些頂點的距離為 、有限值或 ?Bellman–Ford 回報甚麼?
解答 · 答案
可達環 的權重為 ,所以 的距離為 。它們不能到達 或 ,後兩者距離分別為 0 及 7。 不可達,距離為 ,即使它們的分量本身也有負環。Bellman–Ford 因 回報有可達負環;基本警告本身不提供這份完整分類。
快速檢查
(負自環與零權重環)
若 ,唯一頂點為 ,主要掃描進行多少次?若有權重為 的自環,會發生甚麼?若權重改為 0 呢?
解答 · 答案
主要掃描有 次,但仍會進行偵測掃描。權重為 時,檢查得到 ,正確回報有可達負環;由 到自己的距離為 。權重為 0 時沒有嚴格改善,距離為 0。零權重環容許無限多條相同權重的遊走,卻不會使權重無下界。