假設路線中的負邊代表回贈:總長度為負的迴路可以反覆走,若之後仍可到達目的地,便沒有最短遊走。Bellman–Ford 方法能區分這種情況、有限的最短距離,以及根本不可達的目的地。
遊走與遞推式
定義 24.1.1
(遊走與邊數受限距離)
設有限有向圖 有 個頂點,起點為 ,每條邊的長度 均為有限實數。遊走可以重複頂點和邊;路徑不重複頂點。遊走長度是各次經過的邊長之和。令 為從 到 、最多使用 條邊的遊走的最小長度;若不存在則定為 。令 為所有 到 遊走長度的下確界;沒有遊走時定為 ,亦可能為 。
空遊走長度為零,因此 ,其餘 。
命題 24.1.2
(邊數受限的遞推式)
對 ,約定 ,並把沒有進入 的邊時的內層最小值定為 ,有
證明
(按是否用上最後一條邊分情況)
合資格遊走要麼最多使用 條邊,要麼恰用 條,最後一條為某個 。後者的前段最多使用 條邊,長度至少為 ;反過來,在取得該最小值的前段後加上 ,便得到合資格遊走。有限圖中邊數不超過 的遊走只有有限多個,所以有限最小值確可取得。兩種情況取最小值便得遞推式。
每行必須由上一行計算,才有上述邊數意義。原位更新也可用於通常的算法,但一輪內可能沿多條邊傳播,其中間結果未必等於這裏的 。
概念視角代數
Bellman–Ford 即極小加算術中的矩陣冪
令 為由 到 的弧中最短的長度,若沒有這樣的弧則為 ,再把每個對角元素換成它與 的較小者。在以 作「加法」、以 作「乘法」的算術中,定義 。遞推式正好是 ,所以 ,而 的 元素就是至多 條弧的 到 遊走的最短長度。
常見錯誤
(把原位更新的一輪當作 那一行)
在下面的表格例子中,按所列次序對各邊做一輪原位更新:先得 、,再經 得 ,,再經 得 ,然後經 得 。僅一輪後 已是 ,但 :沒有一條邊的遊走能到達 。最終標號仍然正確,但「最多 條邊的遊走」這類陳述只對同步計算的各行成立。
分辨三種距離
計算至 後,對每條滿足 且尾點標號有限的邊 ,標記其終點 ;再標記所有能從已標記點到達的頂點。
定理 24.1.3
(三類目的地的精確判別)
已標記頂點的距離為 。沒有標記且 的頂點不可達。其餘頂點的距離有限,等於 ,並由一條簡單路徑取得。因此可由起點到達的負迴路,只有在它也能到達目的地時才影響該目的地。
證明
(改善暴露負迴路,負迴路迫使改善)
若某邊能在第 行後改善終點,取一條取得其有限尾點標號的遊走,接上該邊,得到一條至多 邊、比終點標號嚴格更短的遊走。它必重複頂點,且分解出的迴路至少一個為負;否則刪去全部非負迴路便得到不超過 邊、長度不增的遊走,產生矛盾。這負迴路可從起點到達,也能通往被標記終點及其所有後繼;反覆走該迴路,長度便趨向負無窮。
反之,取任何從 可達的負迴路。其頂點均有有限的 標號,因為可達頂點有至多 邊的簡單路徑。若迴路上沒有一條邊可改善,將各式 沿迴路相加,便得零不大於負的迴路長度,矛盾。因此至少一個迴路頂點被標記,並傳播至其所有後繼。未標記的可達目的地,其任何遊走都不能經過負迴路;刪去非負迴路後得到長度不增的簡單路徑。有限多條簡單路徑之中有最短者,且它至多使用 邊,故其長度就是 。同理,可達頂點必有有限標號,所以無窮標號表示不可達。
證明透視
標記為何既不遺漏也不多報
證明包含三個獨立論斷。第 階段後仍有改善,會給出至多 邊的遊走,於是某頂點重複,迴路分解中必有負迴路。可達負迴路經伸縮求和必給出改善。未標記的可達目的地有有限距離,並由簡單路徑取得。
關鍵一步:若迴路上沒有邊可改善,標號 在該迴路上滿足 ,即構成勢能,而勢能不能與負迴路並存。可達性正是在這裏用上:它令這些標號有限,求和才有意義。
缺了甚麼會出錯:若改用非嚴格比較,零長度迴路會被誤報(第 4 道練習)。若省去傳播一步,迴路上的頂點可能被漏掉:在第二個表格例子中,邊 給出 ,與 相等,所以 從來不是改善邊的終點,但 。
如何收結:階段數上限 正是簡單路徑的邊數上限;排除負迴路後,之後不可能再出現更短的遊走。
當 時仍適用:先用 ,額外掃描會發現負自迴路。零長度迴路可以重複,卻不會令距離變為負無窮,也不會僅因可重複而觸發嚴格改善。
完整算例
例題 24.1.4
(有負邊但沒有負迴路)
取邊 、、、、、、、。唯一有向迴路 的長度是 。逐行由上一行計算:
| 最多邊數 | |||||
|---|---|---|---|---|---|
| 0 | 0 | ||||
| 1 | 0 | 4 | 5 | ||
| 2 | 0 | 4 | 2 | 8 | 9 |
| 3 | 0 | 4 | 2 | 5 | 6 |
| 4 | 0 | 4 | 2 | 5 | 6 |
例如 ,而 。第 4 行之後沒有邊可再改善。路徑 的長度為 ; 也長 6,均取得已證實的最短距離。負邊不妨礙 Bellman–Ford;Dijkstra 的標準證明則需要非負邊長。
例題 24.1.5
(負迴路與標記步驟)
現在只把 的長度由 改為 ,迴路 的長度便是 。第 至 行不變。第 3 行給出 、 及 。第 4 行給出 、、,而 仍是 。
額外掃描找到兩條改善邊: 給出 , 給出 。所以 和 是被標記的終點。由 經 傳播,標記 。因此 。重複迴路不能反向通往 或 ;它們的距離仍為 4 和 0,也沒有被標記,因為沒有邊從迴路通向它們。
例題 24.1.6
(含負迴路的不可達分量)
取頂點 及邊 、、,故 。迴路 的長度為 ,但沒有邊由 進入 。從 起,每行對 都是 。
額外掃描中,迴路上的邊尾點標號為 ,因而被排除,沒有任何標記。定理於是把 判為有限距離 ,把 判為不可達。負迴路存在,卻與從 出發的每個距離無關;正是尾點標號有限這個條件,令它不被誤報。
反例模式
負邊不等於負迴路
一個看似合理的說法是:有負邊便令距離無界。若圖中只有長度 的邊 ,則 、。額外掃描比較 與 ,沒有嚴格改善,沒有標記,距離是有限的 ;單一負邊不能重複走。反過來,可達負迴路若不能到達 ,也不會令到 的距離變為負無窮,正如第 2 道練習所示。判別定理所需的是:可達、且能到達目的地的負迴路。
常見錯誤
(只標記改善邊的終點)
額外掃描只找到改善邊的終點。位於迴路上或其後的頂點,即使不是這種終點,距離也可能是 ,正如第二個表格例子中的 。報告有限距離之前,必須沿所有邊傳播標記。
還原路徑與運算量
對有限、未標記的目的地,可在每個狀態 記錄其值承繼自上一行,還是由某條進邊取得。由 向前追蹤,每次減少 ;把記錄的邊倒序便得到取得最小值的遊走。刪去重複頂點形成的迴路:對未標記目的地它們均非負,若刪掉正迴路會與最優性矛盾,所以可得到最短簡單路徑。相同標號可任選一個來源。每點只存一個前驅而不小心處理更新,並不等同記錄每個階段的選擇。
以鄰接表計算,初始化與 次同步掃描連同複製各行需 時間;標記及可達搜尋需 。兩行距離只需 空間;直接保存各階段還原選擇需 。這是算術運算次數,實際位元複雜度取決於邊長的表示。額外掃描有改善表示存在可達負迴路,並不表示每個目的地都受影響。
練習
快速檢查
(已知 、、,求距離並解釋為何沒有負迴路。)
解答 · 答案
經 的路長 ,小於直接路線的 0,故答案為 。所有邊均向前,沒有有向迴路。
快速檢查
(已知 、、,沒有其他邊。分類 。)
解答 · 答案
的距離為 0;反覆自迴路令 的距離為 ; 的距離為 3,因迴路不能到達 。
快速檢查
(,邊為 、、。求 ,指出額外掃描中可改善的邊。)
解答 · 答案
同步計算得 、,以及 、。邊 給出 ,標記 ,再傳播至 。
快速檢查
(為何把嚴格改善換成非嚴格比較會錯判零迴路?舉例。)
解答 · 答案
起點有一條零長度自迴路時,;等號並非改善,所有遊走長度均為零,距離有限。