動機
廣度優先搜尋使經過的邊數最少。邊的費用不同時,邊數最少卻未必總費用最低:一條昂貴的直達邊,可能不及兩條便宜的邊。我們需要比較累計權重,而不只是佇列中的層數。
Dijkstra 的規則是反覆把暫定距離最小的頂點定案。尚未檢查所有路線,為甚麼已經可以認定這個值正確?答案在於一條經過已定案集合邊界的路徑,以及證明中一個恰好用到非負性的地方。給規則冠以「貪心」之名,並不能代替正確性證明。
本節還區分求出答案與核驗答案。一組距離若配有適當的前驅邊和次序,只需掃描一次圖便能證明最優性。這樣的證書既能揭示負邊導致的算法失敗,也能解釋為甚麼只挑等號成立的邊還不夠:它們必須真正連回源點。
定義
定義 5.5.1
(帶權遊走、距離與暫定標號)
設 為有限有向多重圖,,。允許平行弧與自環;每條弧有獨立身份及有限實權 。固定源點 。遊走可以重複頂點,路徑則沒有重複頂點;長度是各弧權重之和。源點 的空遊走長度為零。
記 為從 到 的遊走長度的下確界;沒有這樣的遊走時,定義為 。算法部分假設每條弧滿足 ;後面的證書定理則明確允許任意有限實權。
暫定標號 或是某條候選遊走的有限長度,或為無窮。已定案頂點已被選出,其標號視為最終值。對 到尚未定案頂點 的弧做鬆弛:只有候選值 嚴格更小時才替換 ,同時儲存這條實際弧作為 的前驅。不要對無窮標號進行加法。
所有比較先按精確運算理解。我們先計算加法、比較及索引操作次數,再單列整數的位成本。本節以陣列掃描實現,不預先假設優先佇列。關於樹與廣度優先搜尋的一節提供無權可達性和 BFS 的背景。
定理/命題
定理 5.5.2
(非負權最短遊走可以選為路徑)
若所有弧權非負,每個可達頂點都有一條從 出發、至多含 條弧的最短路徑。因此距離有限且能取到,並且 。不可達頂點的距離為無窮。
定理 5.5.3
(最小暫定標號可以安全定案)
初始化 ,其他標號為無窮,所有頂點未定案。反覆從未定案頂點中選取標號最小者;若最小值為無窮便停止,否則將它定案,並鬆弛其指向未定案端點的出弧。平局可任意處理。
每個定案標號都等於真實距離。結束時,已定案頂點恰為可達頂點,其前驅邊能夠恢復最短路徑。陣列實現需要 次精確操作,連同圖共用 個儲存字。
定理 5.5.4
(可以單獨核驗的最短距離證書)
本定理允許任意有限實權。給定含 的集合 、 上的有限標號且 ,以及取值於 的次序號,源點次序號為零。要求:
- 沒有弧從 指向 外。
- 內每條弧都滿足 。
- 每個 內非源點 都有來自 內的前驅弧,前驅次序號嚴格較小,且 。
那麼 恰為源點可達集合,其標號就是真實距離;其他頂點均不可達。只需 次精確操作檢查這些局部條件,無須重跑最短路算法。
證明思路或證明
先刪去閉遊走,再證明最小值存在
證明
(先刪閉子遊走,再在路徑中取最小)
取一條到達目標的遊走。若某頂點重複出現,兩次訪問之間是一段權重非負的閉遊走。刪去它,端點不變,長度不會增加。不斷刪除,每次弧數減少,最終得到路徑。
有限多重圖只有有限條簡單路徑:每條至多 條弧,弧都取自有限集合。可達目標至少有一條路徑,因此這些路徑長度中存在最小值。刪圈論證說明它不大於任何遊走長度,所以它實現了距離。源點的空遊走長度零,又沒有負長度遊走,故距離為零。權重為零的閉遊走同樣可以刪除;無需每次都嚴格縮短長度。
找到貪心證明中使用非負性的準確位置
證明
(沿最短路徑上首個未定案頂點對定案作歸納)
整個過程中,每個有限標號都是某條實際源點遊走的長度。開始時由空遊走見證;鬆弛時在已有遊走末尾接一條實際弧。因此有限標號不可能低於真實距離,也不可能出現在不可達頂點上。
源點首先定案且標號正確。歸納假設此前定案頂點全部正確,設 是下一個有限最小標號頂點。取一條 到 的最短路徑 ,令 為 上首個未定案頂點, 為它的前一頂點。源點已經定案,所以 存在。 定案時, 還未定案,故該弧已被鬆弛。此後標號只會下降,於是
第一步用最小值選擇,第二步用 的正確標號。真實的 距離不大於 到 的那條特定前綴。最後一步才使用非負性:剩餘後綴不能降低總長度。遊走見證又給出反向不等式,因此 標號正確。
如果最小標號為無窮時仍有可達頂點未定案,取到它的任意源點路徑。首個未定案頂點前面是已定案頂點;後者早已透過鬆弛給前者一個有限標號,矛盾。至多定案 個頂點,故算法終止且定案集合準確。
證明透視
貪心是選擇規則,前綴不等式才是證明
最小值選擇把當前頂點與真正最短路徑上的首個未定案頂點比較。鬆弛用路徑前綴約束後者標號;非負性再把前綴長度壓到完整最優值以下。存在負後綴時,最後一步可能失敗,即使此前每個定案值都正確。
零權圈不會使算法前驅形成圈
證明
(定案次序使前驅無圈)
按定案先後給頂點次序號。前驅只由已經定案的頂點設定,而被更新端點尚未定案,所以端點最終定案時,其前驅次序號嚴格更小。嚴格改進時,前驅與改進後的標號一同更新;相等候選不改變前驅。
每個有限非源點標號都來自鬆弛。沿前驅回溯,次序號嚴格下降,不會成圈;只有源點無須前驅,故最終到達源點。各弧上的等式相加,恢復路徑的長度就是最終標號。平行弧要求保留實際選擇的弧身份,不能只記兩個端點。
避免圈靠的是次序號,而非距離嚴格增加,故零權弧沒有問題。算完距離後隨意挑一些緊弧,不會自動獲得同樣的保證。
雙向證明獨立證書
證明
(次序給出可達性,不等式給出下界)
對滿足三個條件的任意證書,嚴格下降的前驅次序先保證每個 內頂點有一條 內源點路徑。有限下降鏈不可能循環,只有 可以沒有前驅。反過來,沒有弧離開 ,所以源點遊走不可能到達外部。 恰為可達集合。
對任意從 到 的遊走,沿弧累加不等式。中間標號相消,,得到 不大於該遊走長度。因此它不大於所有候選長度的下確界。緊前驅路徑又恰好有長度 ,故下確界也不大於 。兩邊合起來即為相等,並證明最小值取到。
這裏沒有使用權重非負。因此帶負弧的圖也可能有有效證書,儘管貪心算法不再普遍正確。可達集合之外的負圈與這個單源證書無關。逐點檢查歸屬、次序範圍和前驅身份,再逐弧檢查緊性及不等式,只需一次點弧掃描。
算法輸出也具備這樣的證書。前驅和次序已經證明正確。若有弧從定案集合離開,它在停止前就會提供另一個有限候選,矛盾。最後,真實距離滿足所有邊不等式:在到弧尾的最短路徑後追加該弧即可。
概念視角算法
路徑給上界,不等式給匹配的下界
展示一條費用為 的源點路徑,只能證明最優值至多為 。邊不等式則保證每條競爭遊走至少花費 。前驅路徑與不等式是互補證據;單獨一個暫定標號還不能證明最優性。
按實際儲存方式計算成本
儲存出弧鄰接表、標號、前驅弧和定案標誌。每次掃描全部 個頂點選取最小者,至多 次,所以掃描成本為二次。每個定案頂點的出弧表只掃描一次,鬆弛總數至多 。初始化與記錄次序也包含在該界內,圖和陣列總儲存量為 的線性量。輸出一條路徑時回溯前驅並反轉列表,輸出本身可能含 個頂點。
若整數權重在 與 之間,最終有限距離至多 ,臨時鬆弛候選可安全界為 。標號、弧身份及循環索引需要
位,無窮另設標誌。在把尋址作為基本操作的索引陣列模型中,按這個位長計算加法、比較和索引算術,得到它乘 的算術位成本。精確實數證明本身不保證有限精度實現或誤差界;更快的優先佇列界也需要另證數據結構成本。
例題詳解
例題 5.5.5
(定案之前,一條路線兩次改進)
頂點為 。弧及權重為:,,,,,,。 沒有任何關聯弧。
定案 後, 標號為 、。定案 , 改為 , 得到 ;定案 , 改為 , 得到 ;定案 , 改為 。隨後定案 ,在無窮的 之前停止。定案順序 ,對應標號 。
的前驅路徑為 ,費用 。直接經 的另一條路線費用十一。 到 的弧在最終標號下不是緊弧:候選 大於 的真實距離 。證書要求每條弧滿足不等式,只有所選前驅弧必須取等號。
例題 5.5.6
(零權平局仍有無圈前驅)
弧 、、、 的權重都為零, 和 的權重均為 。定案 後, 標號均為零,前驅均為 。若先定案 ,其到 的相等候選不覆蓋 的前驅;它可將 標號設為 、前驅設為 。隨後定案 ,相等的 候選也不覆蓋舊值。
儘管 形成零權圈,所有前驅仍回到 。反向處理平局會得到另一棵有效最短路樹。相等的最優距離,並不要求次序號相等,更不允許前驅成圈。
例題 5.5.7
(證書能夠處理負弧)
,,。令 ,標號 、、,次序為 ;前驅選 和 。
兩條前驅等式成立,剩餘弧滿足 。因此證書直接證明這些距離,包括負距離,無須依賴非負權算法定理。這不表示貪心定案在所有含負邊圖上都正確。
常見錯誤
反例模式
負後綴破壞過早定案
,,。 的真實距離為零,但算法在選擇 前已把 定案為 。由於不再鬆弛定案頂點,最終 的標號錯誤。所得證書在弧 的不等式失敗: 不成立。圖中沒有負圈;單條負弧已經足以造成失敗。
常見錯誤
(BFS 層數不是帶權距離)
不要把 BFS 的邊數層次當作帶權距離。在第一個例題中, 沿 只離 兩條弧,但該路線費用為 ,而四條弧的路線 只需 。
常見錯誤
(永不回到源點的緊前驅)
不要把任意緊前驅當作源點路徑證書。在零權例題中,選 和 都是緊的,因為 之間的四條弧權重都是 ,三個標號也都是 ;但從 沿前驅回溯永遠回不到 。排除這種情況的正是嚴格次序條件。
常見錯誤
(無窮不是很大的有限費用)
無窮表示沒有路線,不是很大的有限費用。若用 之類的哨兵值代替 ,並對它加上權重,不可達頂點便可能得到標號 ;檢查哨兵值的停止條件就會把它當作已到達。
本節處理單源距離;使邊權總和最小的生成樹,以及允許負邊的最短路算法,是不同問題。
只要從源點到達不了負權圈,逐輪鬆弛所有弧便可行,只是代價較高。
自然延伸的下一個問題
有負權弧時,怎樣計算距離?
只要從源點到達不了負權圈,逐輪鬆弛所有弧便可行,只是代價較高。
若從 到達不了任何負權圈,刪去閉子遊走仍不會增加長度,所以最短遊走可取為簡單路徑,至多 條弧。進行 輪,每輪鬆弛所有弧:第 輪後,每個標號至多是弧數不超過 的源點遊走的最短長度,而標號永不低估。這個 Bellman–Ford 程序用 次運算;若第 輪仍有標號改進,便揭示了一個可到達的負權圈。上面的證書可以檢查它的輸出。
總結
非負權既保證最短遊走可以選成路徑,也使最小暫定標號能安全定案。從較早定案頂點發出的嚴格鬆弛,即使遇到零權圈也會產生有次序的前驅路徑。另一方面,有根緊路徑配合邊不等式可獨立證明精確距離,將答案的構造與最優性的核驗區分開來。
練習
快速檢查
(在第一個例題中只將弧 的權重由 改為 。求 的新距離及一條到 的最短路徑。)
解答 · 答案
的距離仍為 ,由 到達。 的距離現為 ,經 ; 的距離為 ,經 ; 仍不可達。 定案後 標號為 ,可先於 定案,其 候選為 。較晚經 得到的 候選 不會改進它。新路徑費用 。
快速檢查
(令 孤立,另外兩個頂點 之間有雙向零權弧。三點都標零, 互為前驅。為甚麼邊不等式和緊性都成立,卻不是有效距離證書?)
解答 · 答案
每條弧權為零,端點標號相等,所以不等式及所選等式都成立。但 均不從 可達。嚴格前驅次序同時要求 的次序小於 的, 的又小於 的,不可能。次序條件拒絕假圈,使緊邊真正成為源點路徑;只憑可行不等式與局部緊性不能斷定標號正確。
快速檢查
(所有弧權為一時,說明帶權距離為何等於 BFS 層數。再分析 、 的反例。)
解答
單位權時,每條遊走的長度就是弧數,最小化兩者是同一件事。因此真實帶權距離等於 BFS 已證明的可達層數;不可達點按兩種約定都是無窮。
所給帶權圖中,BFS 將直達弧 看成一條邊的路線,但其費用為四。經過 的兩條邊費用二,反而更便宜。帶權距離必須比較累計費用,這正是暫定標號所保留的資訊。