Bellman–Ford 一節以反覆鬆弛處理任意實數權重,0–1 BFS 一節則利用權重只有 的特性。本節討論其餘情況下最常用的兩個通用算法。Dijkstra 算法在所有權重非負時計算單一源點的距離,比 Bellman–Ford 快得多;Floyd–Warshall 則以「允許使用的中間頂點集合」為動態規劃的階段,計算所有有序頂點對之間的距離。兩者都依賴同一個基本事實:最短路徑由最短路徑組成。
1. 設定與約定
定義 16.3.1
(距離與鬆弛)
設 為有限有向圖,、,權重函數 。一條途徑的權重是其各邊權重之和; 表示從 到 的途徑的最小權重,若不可達則為 。無向圖把每條邊換成兩條權重相同的有向邊。允許平行邊與自環。
鬆弛。 給定每個頂點的暫定標籤 ,鬆弛邊 即:若 ,則令 。全程每個有限標籤都是從源點出發的某條真實途徑的權重,所以永遠有 。
最優子結構。 若 是到 的最小權重途徑,則每個前綴 也是到 的最小權重途徑;否則以較輕的前綴替換,整條途徑便會變輕。
2. Dijkstra 算法
假設。 每條邊都滿足 。固定源點 。
算法維護標籤 與「已確定」頂點集合 ,每次取出標籤最小的有限未確定頂點 ,把它確定下來,並鬆弛 指向未確定頂點的所有出邊;已確定頂點的標籤不會再改變。用二叉最小堆實作時,堆中存放 (標籤, 頂點),取出過時項目時直接捨棄。
for each v: d[v] = infinity; settled[v] = false
d[s] = 0
H = min-heap containing (0, s)
while H is not empty:
(k, u) = extract_min(H)
if settled[u] or k != d[u]: continue # stale entry
settled[u] = true
for each edge (u, v, w):
if not settled[v] and d[u] + w < d[v]:
d[v] = d[u] + w
insert (d[v], v) into H
return d
定義 16.3.2
(已確定頂點與過時項目)
當頂點 從堆中被取出,而取出項目的鍵等於它當時的標籤 時,稱 已確定;此後 不再改變。若 已確定,或 ,則堆項目 是過時的;過時項目直接丟棄,不作任何鬆弛。
定理 16.3.3
(Dijkstra 算法的正確性)
若所有權重非負,則頂點 被確定時有 ;終止時對每個頂點 都有 ,不可達者為 。
證明
(對確定次序作歸納)
對確定頂點的先後次序作歸納,證明每個頂點在被確定的一刻已正確。第一個被確定的是 ,,因為非負圖沒有負權重途徑。
設下一個被確定的是 ,其標籤為 ,並設先前已確定的頂點都正確。 是某條途徑的權重,故 。假設 以導出矛盾。此時 ;取一條從 到 的最小權重途徑 ,令 為 上第一個在確定 之前尚未確定的頂點。 本身未確定,所以 存在;又 ,因此 在 上有已確定的前驅 。由歸納假設 ,而 被確定時邊 已被鬆弛,故其後 。由最優子結構, 到 的前綴是到 的最小權重途徑,所以 。於是 ,結合 得 。由於 從 到 的餘下部分權重非負,。這表示未確定的 有小於 的有限標籤,堆中有鍵為 的有效項目,與「取出鍵最小的項目 」矛盾(若 ,則 ,直接矛盾)。故 。
從 可達的頂點最終都會被確定:否則某條自 出發的路徑上有邊 , 已確定而 可達但未確定; 被確定時鬆弛該邊,令 得到有限標籤及堆內項目,堆未空前它必被取出。不可達頂點永遠得不到有限標籤。
證明透視
證明在哪裏用到非負性
證明只有一步不顯然:它不拿 與每個頂點逐一比較,而是沿著最小權重的路徑 走,停在第一個尚未確定的頂點 。三個事實在這個邊界頂點匯合。(1) 的前驅 已確定,所以由歸納假設 。(2) 被確定時邊 已被鬆弛,故 ,最後一個等號來自最優子結構。(3) 從 到 的尾段權重至少為 ,所以 。(1) 和 (2) 完全沒有看過任何權重的正負號,只有 (3) 需要 。三者合起來給出 ,堆會先取出 而不是 ,矛盾。沒有非負性時,鏈條恰好在 (3) 斷開;下文負權邊一節的輸入中就有 。
命題 16.3.4
(二叉堆 Dijkstra 的開銷)
採用惰性刪除與二叉最小堆的 Dijkstra 算法至多向堆插入 個項目,時間為 ,空間為 。
證明
(計算確定次數與堆項目數)
每個頂點只被確定一次,所以每條邊至多被鬆弛一次。每次成功鬆弛插入一個堆項目,故堆至多收到 個項目,每次插入或取出耗時 。總時間為 ;當 且無平行邊時即 。空間為 。若改用陣列掃描代替堆,時間為 ,對非常稠密的圖更合適。
3. 例題:含過時項目的 Dijkstra
例題 16.3.5
(含過時堆項目的 Dijkstra)
邊:(4)、(1)、(2)、(1)、(5)、(3)、(6)。
| 取出 | 動作 | 其後的堆 |
|---|---|---|
| 確定 ;、 | ||
| 確定 ; 由 改進為 ; | ||
| 確定 ; 由 改進為 ; | ||
| 過時, 已確定 | ||
| 確定 ; 由 改進為 | ||
| 過時 | ||
| 確定 | ||
| 過時 | 空 |
距離為 、、(經 ,而非權重 4 的直接邊)、、,路徑為 。
4. 為甚麼負權邊會令 Dijkstra 失效
反例模式
負權邊令 Dijkstra 失效
聲稱:只要圖中沒有負圈,即使部分邊權為負,Dijkstra 算法仍會輸出正確的距離。
取邊 (2)、(3)、(−2)。Dijkstra 先確定 ,再確定標籤為 2 的 ,然後確定標籤為 3 的 。邊 本應給出 ,但 已確定,標籤不再被重新檢視,所以輸出 ,而真實距離是 。在證明中,途徑 正是 ,未確定頂點 滿足 :尾段 權重為負,不等式 不成立。把所有權重加上同一個常數來消去負數也不能補救,因為邊數較多的路徑會被不成比例地懲罰。
正確的陳述必須保留假設 。權重可為負而沒有負圈時,改用 Bellman–Ford;全點對情形則用下文的 Floyd–Warshall。
5. Floyd–Warshall
定義 16.3.6
(限制中間頂點的最短路徑)
把頂點編號為 。定義 為從 到 、所有中間頂點都落在 內的簡單路徑的最小權重(空路徑使 ),不存在則為 。 時不允許任何中間頂點:
平行邊取權重最小者。假設: 沒有負圈(權重本身可以為負)。
定理 16.3.7
(Floyd–Warshall 遞推式)
若 沒有負圈,則對每個 及所有頂點 ,
證明
(在頂點 k 處拆開路徑)
考慮從 到 、中間頂點在 內的最小權重簡單路徑 。若 不是 的中間頂點,則 已計入 。若是,由於 簡單, 恰好出現一次;在 處切開,得到 與 兩條簡單路徑,中間頂點都在 內,由最優子結構其權重分別為 與 。反過來,兩個表達式各自都是一條中間頂點在 內的真實途徑的權重;又因無負圈,這類最小權重途徑可取為簡單的(刪去圈不會增加權重)。故兩式之最小值恰為 。
當 時,。
D = D0
for k = 1..n:
for i = 1..n:
for j = 1..n:
if D[i][k] + D[k][j] < D[i][j]:
D[i][j] = D[i][k] + D[k][j]
一個矩陣已經足夠。第 輪中第 行與第 列不會改變: 只有在 ,即 時才會改變,而無負圈時 。所以就地讀取的值與讀取 的結果相同。時間為 ,空間為 ,與 無關。對無負圈的稠密圖,這與從每個源點各跑一次 Dijkstra 相當;有負權時,它是簡單的選擇。
概念視角代數
把全點對距離看成最小加矩陣的冪
定義 。由於 的對角線為零, 就是從 到 、至多 條邊的路徑中的最小權重。在沒有負圈時,最短路徑可取為簡單路徑,所以 。Floyd–Warshall 則透過逐個加入中間頂點,得到同一個矩陣。
若存在負圈,標準結論是某個對角元 會變為負數,這是常用的檢測方法;但此時矩陣中的其他數值可能不可靠,所以對角線出現負數即表示「停止,經過該圈的距離沒有定義」。
6. 例題:含負邊的 Floyd–Warshall
例題 16.3.8
(含負邊的 Floyd–Warshall)
頂點 ,邊為 (3)、(8)、(−2)、(6)、(1)、(5)。穿過全部四個頂點的圈 權重為 ;其餘的圈( 為 14, 為 14)也為正,故假設成立。以下各行為 。
:第 1 行 ;第 2 行 ;第 3 行 ;第 4 行 。
:只有 的 有限。,。第 4 行 。
:第 2 列在 有限,值為 ;第 2 行為 。,,, 維持 0。
:第 3 列對 為 ;第 3 行為 。,, 維持 0。
:第 4 列為 ;第 4 行為 。第 1 行:,,。第 2 行:,,。第 3 行:,,。
最終矩陣:第 1 行 ;第 2 行 ;第 3 行 ;第 4 行 。驗算 :從 3 出發唯一的出路是 ,權重 。
例題 16.3.9
(負圈出現在對角線上)
頂點 ,邊 (1)、(−3),圈的權重為 。。 時 。對角線上的負數揭示了負圈。
7. 常見錯誤
常見錯誤
(有負邊但沒有負圈)
Dijkstra 的假設是每條邊都滿足 ,並不只是沒有負圈。無圈圖 (2)、(3)、(−2)根本沒有圈,但 Dijkstra 輸出 ,而 。應改用 Bellman–Ford;全點對情形則用 Floyd–Warshall。
常見錯誤
(頂點一被發現就視為已確定)
標籤只有在其項目以當前最小鍵被取出時才是最終的,頂點剛被到達時並不是:較後確定的頂點可能提供更輕的路線。在第一個例題中, 最初得到標籤 ,最終卻是 。
常見錯誤
(關於 k 的迴圈必須在最外層)
Floyd–Warshall 的不變量針對允許的中間頂點集合 ,所以必須先對所有頂點對 完成第 輪更新,才可納入 。若把 放在最內層,某個頂點對在後面的中間頂點尚未組合之前就已結束,需要多個中間頂點的路徑便可能被漏掉。
還有三個須留意的疏忽:
- 沒有跳過過時的堆項目,造成多餘的工作並扭曲運算次數。
- 以有限的哨兵值代表 時計算 :應先確認兩個運算元都是有限值。
- 輸入可能含負圈時,沒有檢查對角線是否有負元素就把 Floyd–Warshall 的矩陣當作有效結果。
練習
快速檢查
(在邊 (2)、(5)、(1)、(7)、(2)上,從 執行 Dijkstra。寫出確定次序與最終距離。)
每次改進都會產生新的堆項目,舊項目隨即過時。
解答 · 答案
取出 :、。取出 : 改進為 ,。取出 : 改進為 。其後 為過時項目;取出 時確定 , 為過時項目。確定次序為 。距離:、、、(路徑 )。
快速檢查
(邊:(1)、(4)、(−5)。Dijkstra 對 輸出甚麼? 又是多少?)
看看 被確定時,邊 會怎樣。
解答 · 答案
Dijkstra 先確定 (、),再確定標籤為 1 的 (沒有出邊),然後確定標籤為 4 的 。邊 因 已確定而被忽略,輸出為 。但途徑 的權重為 ,故 ,Dijkstra 在此給出錯誤答案。
快速檢查
(某圖有 個頂點而沒有任何邊。從 出發的 Dijkstra 會向堆插入甚麼?輸出是甚麼?)
數一數究竟可能發生多少次鬆弛。
解答 · 答案
只會插入初始項目 。它被取出並確定 ;沒有邊可鬆弛,堆隨即變空。輸出為 ,其餘頂點 ,這是正確的,因為其他頂點都不可達。這正是插入數上界 在 時的情形。
練習 16.3.10
(在頂點 、邊 (4)、(5)、(−1)、(2)上執行 Floyd–Warshall,寫出最終矩陣。)
核心
解答(3)
- 1
寫出初始矩陣
:第 1 行 ,第 2 行 ,第 3 行 。(圈 的權重為 。)
- 2
第 與 輪
:只有第 3 行的 有限:,。第 3 行 。
:第 2 列為 ;第 2 行為 。;。
- 3
第 輪與答案
:第 3 列為 ;第 3 行為 。,;,。
最終:第 1 行 ,第 2 行 ,第 3 行 。驗算:,經 。