1. 設定與約定
定義 16.1.1
(途徑與最短距離)
設 為有限有向圖,其中 、,實數權重 ,源點 (故 )。途徑(walk)可重複經過頂點和邊。容許在 處零條邊的途徑,其權重為 。
最短距離定義為所有途徑權重的下確界:
並約定 。
計算約定。
- 我們採用實數 RAM 模型,其中實數的加法與比較均耗時 。
- 是一個哨兵值。對任何實數 ,它滿足 及 。
- 由於權重均為實數,運算式 永不出現。算法從不儲存 ;這個標籤是事後透過可達性才指定的。
- 邊列表可在 時間內列舉所有邊。一般的鄰接表遍歷亦須掃描所有頂點,耗時 。
2. 有界長度距離與遞推關係
定義 16.1.2
(有界長度距離)
定義 為由 到 、最多含 條邊的途徑的最小權重;若不存在這樣的途徑,則為 。對固定的 ,這樣的途徑只有有限多條,故最小值存在。
命題 16.1.3
(有界長度遞推關係)
數值 滿足 ,且對 有 ;並且對每個 :
證明
(d_i 與右方之間的兩個不等式)
記右方為 。我們分別證明兩個方向的不等式。
- ()最多含 條邊的途徑亦最多含 條邊。此外,一條最多含 條邊、到達 的途徑,接上 後,便是一條最多含 條邊、到達 的途徑。因此 中每個候選值都是 所計及的某條途徑的權重。若某項為 ,不等式顯然成立。
- ()取 的一條最優途徑 。若 最多含 條邊,則 。否則 恰含 條邊,故其最後一條邊為某條 。其前綴含 條邊,故 。若不存在任何途徑,則兩邊皆為 。
同步 Bellman–Ford 使用兩個陣列,由 計算 。每一輪掃描所有邊,並且只讀取舊陣列。原地更新(非同步版本)同樣正確,但其中間值不再恰好等於 。這就是我們分析同步版本的原因。
概念視角結構
把各輪看成無圈圖的分層
為每個頂點作副本 。每條邊都把 連到 ,權重為 ;另把 連到 ,權重為 。這個分層圖沒有圈,而 就是從 到 的路徑的最小權重。 中的負圈,在分層圖裏就成為一條沿著各層不斷下降的路徑。
3. 輪後的有限距離
若一個圈包含某頂點 ,使得 且 ,則稱該圈與 相關。
引理 16.1.4
(n−1 輪後的有限距離)
若 可達,且沒有與 相關的負圈,則 ,而且此值為有限。
證明
(刪去非負的閉子途徑)
一條 – 途徑上的每個頂點均可由 到達,並可到達 。因此,這樣一條途徑的任何封閉子途徑 都可分解為與 相關的簡單圈。每個這樣的圈權重均非負,故 。因此刪去 永不會增加權重。重複此步驟,便得到一條最多含 條邊、權重不大於原途徑的簡單路徑。故此每條途徑的權重至少為 ,即 。反方向的不等式 由定義即得。
引理 16.1.5
(相關負圈迫使距離為負無窮)
若某負圈 與 相關,則 。
證明
(反覆繞圈)
由 走到 上的某頂點 ,繞 走 次,再由 走到 。其權重為 ,當 時趨於 。
推論 16.1.6
(距離的三分性)
兩條引理合起來給出三分法:
- 當且僅當 不可達;
- 當且僅當有負圈與 相關;
- 否則 。
4. 額外一輪所證明的事
多計算一輪 ,並設 。
命題 16.1.7
(額外一輪所證明的事實)
設 。(i) 若 ,則存在可由 到達的負圈。(ii) 若存在可由 到達的負圈,則每個這樣的負圈都含有 中的頂點。(iii) 每個 都有 。
證明
(三項結論的證明)
(i) 存在可由源點到達的負圈。
假設不存在可達的負圈。有限距離引理 便給出在可達頂點上 。由於 ,第 輪不會改變任何值。不可達頂點則保持為 。
(ii) 存在可由源點到達的負圈 。
設 為這樣的一個圈。每個 均可達,故 為有限。用反證法,假設對每個 都有 。遞推關係給出
沿 求和,得 ,矛盾。事實上這證明了更強的結論:每一個可達的負圈都包含 中的某個頂點。
(iii) 。
若 為有限,則有限距離引理 的證明會顯示每條 – 途徑的權重至少為 。特別地,,與 矛盾。
證明透視
為甚麼繞圈求和必定閉合
唯一不顯然的一步是 (ii)。假設 上沒有頂點在第 輪改變,便可把遞推關係(關於 的不等式)讀成同一個陣列 的兩個值之間的不等式。沿 把這些不等式相加,所有標籤互相抵消,只剩下 。這次抵消用到可達性:所有 都是有限值,減法才合法;若標籤是 ,就甚麼也抵消不了。論證是對整個圈作反證,所以只證明 上有某個頂點改變,並不能指出是哪一個。(i) 則從另一個方向收尾:若沒有可達的負圈,有限距離引理 已使 在可達頂點上等於 ,第 輪就沒有可改進之處。
額外一輪沒有說明的事。
- 中的頂點不一定位於某個圈上。
- 不在 中的頂點仍可能有 ,因為它可能只是在這一輪中恰好沒有改進而已。
反例模式
X 並不等於負無窮頂點的集合
聲稱: 恰好當 。取頂點 與邊 (1)、()、(1)、(0),故 。圈 的權重為 。依次列出 ,由遞推關係得 、,所以 。然而 在圈上,故 ; 可由該圈到達,故 。因此 (iii) 的逆命題不成立: 只記錄在這一輪有所改進的頂點。正確的陳述是下面的定理 ,在此例中等於 。
定理 16.1.8
(負無窮頂點就是可由 X 到達的頂點)
,即在 中可由 的某頂點到達的所有頂點所成的集合(包括 本身)。
證明
(兩個包含方向)
我們分別證明兩個方向的包含關係。
- ()由 (iii), 的每個頂點均有 。此外, 及 蘊含 。因此這個標籤會沿邊傳播至整個 。
- ()若 ,有限距離引理(逆否命題)給出一個與 相關的負圈 ,滿足 。由 (ii), 包含某個 。於是 沿 可到達 ,而 可到達 ,故 。
最終輸出。 由 出發執行 BFS 或 DFS,並報告:
- 在 上為 ;
- 在 之處為 ;
- 其餘情況為 。
這些情況互不相交。 中的每個頂點均可達,而由 可到達的每個頂點亦然。
兩項區分。
- 不可由 到達的負圈對任何距離都沒有影響,額外一輪亦無法察覺它。其頂點保持為 。
- 可由 到達,但不可由任何可由源點到達的負圈到達的頂點,會保持有限值 。
例題 16.1.9
(哪些頂點的距離是負無窮)
例如,取邊 (權重 1)、(權重 1)、(權重 )、(權重 1),另加一個獨立的圈 ,總權重為 。則:
- ;
- ;
- 。
5. 例題
例題 16.1.10
(含一條負邊的圖上的五輪計算)
頂點為 ,。邊如下:
| 邊 | |||||||
|---|---|---|---|---|---|---|---|
| 權重 | 1 | 3 | 3 | 1 | 5 | 2 |
共有兩個簡單有向圈:,權重為 ;以及 ,權重為 。兩者均非負,故不存在負圈。
| 輪次 | |||||
|---|---|---|---|---|---|
| 0 | 0 | ||||
| 1 | 0 | 1 | 3 | ||
| 2 | 0 | 0 | 3 | 4 | 8 |
| 3 | 0 | 0 | 3 | 3 | 5 |
| 4 | 0 | 0 | 3 | 3 | 4 |
| 5(額外) | 0 | 0 | 3 | 3 | 4 |
此表直接由遞推關係得出。有三項值得核對:
- 第 2 輪中,。
- 第 4 輪中,,這用到了四條邊的路徑 。
- 第 5 輪中,。
全部 輪確實都是必需的。額外一輪沒有改變任何值,故 ,與不存在負圈一致。
例題 16.1.11
(只有一個頂點與一條自環)
設 ,只有一條權重為 的自環 。此時 ,普通輪數 ,並且 。額外一輪計算 。若 ,則 ,所以 且 :這條自環是非負圈。若 ,則 ,所以 且 ,因為繞自環 次的權重為 。即使是最小的圖,也要靠額外一輪才能發現它的負圈。
反例模式
過早定案一個頂點
聲稱:上面的圖沒有負圈,所以標準的 Dijkstra 能算出正確的距離。
Dijkstra 算法的正確性論證需要非負權重。在此假設下,離開已定案集合的路徑日後永不可能變得更便宜。以下是教科書版 Dijkstra 在此圖上的運作(頂點在被取出時即定案):
- 取出 。設 及 。
- 以 1 取出 並將其定案。設 。
- 以 3 取出 。邊 本可把 降至 ,但 已經定案。設 。
- 以 4 取出 。設 。
- 取出 。
輸出為 、、。真實值為 、 及 。
若某變體確實把 降至 ,但從不重新掃描 的出邊,則 仍然是 。負權邊破壞了算法所依賴的不變量。
補救辦法是只在權重非負時使用 Dijkstra;有負邊時改用上述有界長度的輪次,它在第 輪之前不會定案任何頂點。
6. 複雜度
命題 16.1.12
(含額外一輪的 Bellman–Ford 開銷)
含額外一輪及從 出發的最後搜尋的同步 Bellman–Ford,時間為 ,空間為 。
證明
(計算輪數、邊數與儲存空間)
- 輪數。 算法執行 輪: 個普通輪次加上額外一輪。
- 每輪成本。 每輪掃描 條邊並複製一個長度為 的陣列,即 。總成本為 。
- 常見的 界。 先以 時間找出可由源點到達的子圖;記 為其頂點數與邊數。若 ,則 ,故各輪合共耗時 。連同初始搜尋,總計 。若 ,則各輪改為耗時 ,這包括沒有邊的情況及可能出現的自環。
- 由 出發的可達性。 耗時 。
- 空間。 已足以容納圖、兩個距離陣列及搜尋所需。
表示方式的注意事項。 直接列舉邊耗時 ,另加 的陣列初始化或複製。若使用一般的鄰接表,每輪掃描頂點及其邊同樣是 。若圖以鄰接矩陣給出,則每輪掃描耗時 , 輪合共 。
7. 常見錯誤
常見錯誤
(有負圈時把 當作答案)
上面反例中的頂點 有 ,是完全有限的值,但 。 只對沒有相關負圈的頂點才是距離;額外一輪和從 出發的搜尋正是用來處理其餘頂點的。
常見錯誤
(把源點到不了的負圈也算進去)
若從 沒有任何途徑通向某個負圈,它不會改變任何 ,其所有頂點在每一輪中的標籤都保持為 。「整個圖中存在負圈」是另一個問題;本算法回答的是從 出發的途徑的問題。
常見錯誤
(用有限的哨兵值代表無窮)
若把 存成一個很大的有限數 ,則從未到達的頂點沿權重為 的邊鬆弛會得到 ,看起來比 更好。於是未到達的頂點會出現在 中,或得到虛假的有限標籤。使用 前應先確認它是有限值,或使用滿足 的真正無窮。
8. 練習
快速檢查
(在五輪例題的圖中,只做 輪能否讀出 ?寫出 與 。)
看看通往 的最佳路徑含有多少條邊。
解答 · 答案
不能。表中 ,但 ,由四條邊的路徑 取得,並於 才首次出現。含 條邊的最短路徑需要 輪。
快速檢查
(頂點 (故 ),邊 (2)、()、(1)、(4)。求 及每個 。)
先算 與 ,再用 。
解答 · 答案
圈 的權重為 。對 ,各輪給出 、,所以 。於是 ,即 ,而 。注意 與 是不在 內的負無窮頂點。
快速檢查
(某圖有一個源點 到不了的負圈。該圈上的 是多少?它為 貢獻哪些頂點?)
哪些標籤有可能變成有限值?
解答 · 答案
該圈上每個頂點的 ,因為沒有從 到它的途徑。它們的標籤在每一輪都保持 ,所以沒有任何一個屬於 。算法看不見這個負圈,這正是正確的。
練習 16.1.13
(證明:若 在每個頂點上成立,則對所有 都有 。)
核心證明
解答(3)
- 1
把遞推關係寫成映射
令 把陣列 送到陣列 。則對每個 都有 。
- 2
對 k 作歸納
關鍵一步
時結論顯然成立,而 就是假設。若對某個 有 ,則 。
依據: 每個陣列只由前一個陣列決定。
- 3
得出結論
∎所以對所有 都有 ,再多做任何一輪也不會改變任何標籤。