動機
單源最短路徑算法只能給出由某個起點出發的距離,但有時需要求出每一對有序頂點之間的距離。Floyd–Warshall 算法圍繞「哪些頂點可以出現在路徑內部」來組織問題:在每一階段,它考察多容許一個頂點作為中間頂點後,某個距離是否能夠改進。
本單元容許負權邊,但不容許負權圈。若沒有這一假設,有限的最短距離未必存在:反覆繞行一個可達的負權圈,可以令途徑的權重無限下降。我們把不可達的頂點對的距離視為 。
定義
定義 3.6.1
(經中間頂點的距離)
設 是頂點為 的有限有向圖,邊權為實數,且不含負權有向圈。平行邊可以用其中權重最小的一條取代。途徑的權重是其各邊權重之和。由某頂點到其自身的長度為零的途徑,權重為零。對 ,定義 為由 到 且內部頂點均屬於 的途徑的最小權重;端點不受限制。若不存在這樣的途徑,則取值 。
初始化時,令 ;對 ,令 為最輕的直接邊的權重,若無邊則為 。在沒有負權圈的前提下,自環的權重非負,因此對角線取零長度途徑的初始化是正確的。計算候選值時,對有限的 約定 。
定理
定理 3.6.2
(中間頂點遞推式)
對 ,
第 階段之後,這些元素即為全源最短途徑距離。
定理 3.6.3
(原地計算)
由 出發,依次處理 ,並對每個有序對 ,將 替換為 。在無負權圈的假設下,所得結果等於 。該算法使用 次算術/比較運算和 個距離元素。
證明思路或證明
證明
(在新頂點處分割最短途徑)
在沒有負權圈時,只要存在任何容許的途徑,就存在權重最小的容許途徑:不斷去掉含重複頂點的、權重非負的圈,直至剩下一條簡單路徑。若某條最短路徑內部不出現 ,則其成本至少為 。否則取一條最短簡單路徑,它至多經過 一次,在 處將其拆開。兩段子路徑的內部頂點都屬於 ,所以其成本至少為 。當 是端點時,同樣的推理仍然成立,只需用一段零長度子途徑。
反過來,實現第二項兩個距離的任意兩條途徑,可以在 處連接起來,得到第 階段容許的一條途徑。第一項對應的途徑同樣是容許的。若某一項為無窮,則它不提供有限的候選值。這兩個不等式證明了遞推式。在第 階段,所有頂點都可以作為內部頂點,因此得到不受限制的最短途徑距離。
證明透視
無負權圈的假設用在何處
不顯然的一步,是先取一條最短的簡單途徑再分割:這樣 至多出現一次,兩半的定義才明確,而且各自的內部頂點都在 之中。無負權圈的假設正用在這裏,用來說明去掉圈不會增加權重,所以存在簡單的最小者。相反方向的上界則無需這樣小心,因為在 處連接兩條容許的途徑,即使結果有重複頂點,仍然是容許的。論證對階段 歸納,從第零階段的直接邊表出發;到第 階段,內部頂點不再受限。若沒有這個假設,分割就失去意義,因為最小值不存在,下面的反例正說明這一點。
證明
(階段內的行和列保持不變)
對於原地更新:對角線始終為零,因為權重為負的閉途徑必然包含負權圈,而這已被假設排除。在第 階段,更新 時是將它與 比較;更新 時同理,它也保持不變。因此在整個階段中,用來產生候選值的第 行和第 列保持其第 階段的取值。其餘每個單元都恰好用這些不變的元素,由其先前的值更新一次,這正好實現了遞推式,且與 的處理次序無關。三重嵌套迴圈給出運算次數的界,而表中共有 個元素。
證明透視
為甚麼這裏原地更新是安全的
證明需要第 階段的行和列在其他單元更新期間保持不變。由無負權圈假設保證的零對角線提供了這一不變量。
例題詳解
例題 3.6.4
(中間頂點改進了一條路徑)
設 的權重為 , 的權重為 , 的權重為 。容許 作為中間頂點,會得到候選值 ,所以由 到 的距離變為 。當不存在負權圈時,負權邊不會影響這一推理。
例題 3.6.5
(不可達的頂點對)
若既沒有由 到 的直接邊,也沒有任何途徑能由 到達 ,則每個包含不可達段的候選值都是 ,最終元素仍為 。在沒有證明某個有限數大於所有相關的有限路徑成本之前,不可以把它換成一個很大的有限數。
常見錯誤
常見錯誤
(把每條負權邊都當作負權圈)
權重為 的邊不一定令最短路徑問題失效。問題出在存在一個可達的圈,可以重複繞行且總權重為負。含 的那個例題中有負權邊,但在所示的圖裏沒有圈。
反例模式
放棄無負權圈的假設
斷言:遞推式對任何實數權重的有向圖都能算出最短途徑距離,包括含負權圈的圖。取兩個頂點 ,邊 的權重為 ,邊 的權重為 ,這個圈的權重為 。重複走這個圈,得到由 到自身、權重為 的途徑,因此這一對沒有有限的最小值。原地算法按行優先次序處理各對時,由 出發,最後得到 :對角線元素為負,所以這張表並不是距離表,而且結果取決於迴圈恰好運行了多少步。修正方法是保留假設:不存在權重為負的有向圈,或另用算法去檢測這樣的圈。
該定理計算的是距離;若要重構路徑,還需要額外的前驅資訊,並需要仔細處理並列的情況。
反例模式
把階段下標放在最內層
斷言:三重迴圈可以按任意次序嵌套,例如把 放在最內層,只掃描一遍仍得到距離。取頂點 ,邊 、、 的權重都是 ,因此由 到 的距離是 。若 為最內層迴圈,各對 按行優先次序處理,則在求 時, 與 尚未得到改進後的值 和 :候選值為 與 ,所以它仍是 ,而第 行不會再被處理。修正方法是採用所述的嵌套,以階段 為最外層,先完成階段 的所有頂點對,再進入階段 。
正確理解狀態
下標 限制的是內部頂點,而不是端點。在第零階段,直接邊沒有內部頂點,即使某個端點的編號很大,它也是容許的;零長度途徑同樣是容許的。在第 階段,端點 和 可以等於 ;由於在假設下對角線距離為零,遞推式仍然有效。
動態規劃的不變量是:完成第 階段後,每個表項是僅以頂點 作為內部頂點時的最優距離。這並不表示這些頂點必須全部被用到。多容許一個頂點,只會令距離保持不變或變得更好,因此 。若某次計算令一個有限的表項變大,則說明它違背了遞推式。
例題 3.6.6
(一個完整的三頂點表)
設頂點依次為 ,邊為: 權重 , 權重 , 權重 , 權重 。兩個有向圈的權重分別為 和 ,所以不存在負權圈。初始表為
容許 後, 的成本為 。容許 後, 的成本為 。容許 後, 的成本為 。最終的表為
未提及的元素保持不變。每一次改進都有一條實際連接而成的途徑作為依據。
概念視角代數
同一張表看成矩陣乘積
把加法換成取最小值、乘法換成加法:兩張表的乘積定義為 。設 為初始表,則 給出至多兩條邊的最佳途徑, 給出至多 條邊的最佳途徑;由於最短途徑可取為簡單路徑,這已足夠。因此在這種乘積下 。在三頂點例子中, 已等於最終的表。
一個表項可能有多條取到最小值的途徑。遞推式只需要最小權重,所以並列時可以不作更新。若還要求給出路徑,可以另設一個見證結構,記錄一條直接邊或一個起改進作用的中間頂點。要由最終的原地表重構路徑,必須為這些見證建立不變量,特別是在存在零權圈或並列路徑時。本單元證明的是距離的計算,並不聲稱某種具體的路徑重構實作是正確的。
為甚麼可以去掉圈
任何閉途徑都可以分解為若干有向圈。在假設之下,每個這樣的圈權重非負,所以去掉一段含重複頂點的閉途徑段,不會令途徑的總權重增大。重複這一操作,在兩端點不同時得到一條簡單路徑,在兩端點重合時得到空途徑。去掉頂點不會引入容許集合之外的內部頂點。由於有限圖中固定一對頂點之間只有有限多條簡單路徑,只要這一對頂點可達,最小值就存在。
這一論證容許零權圈。去掉一個零權圈後,權重可能保持不變而不是嚴格減小,但仍然得到一條取最小值的簡單路徑。負權邊同樣是容許的:關鍵在於每個有向圈的總權重。只要不存在可重複繞行、令下確界無下界的負權閉途徑,最短簡單路徑就可以包含負權邊。
遞推式中上界方向使用的是連接操作,即使每一段都是簡單的,連接後的途徑也可能含有重複頂點。這在 的定義中是容許的。連接後的途徑滿足內部頂點的限制:連接點是 ,其餘內部頂點都出現在兩段子途徑之一中。如有需要,還可以去掉非負權圈而不增加其權重。這就是兩個不等式能夠配合起來、而無需假設連接結果本身是簡單路徑的原因。
三重迴圈的下標
外層下標決定容許作為中間頂點的集合。對固定的 ,兩層內迴圈枚舉所有起點和終點。由於第 行和第 列在該階段內不變,在定理的假設下,內兩層迴圈採用任一次序都可行。若把 移到其他迴圈的內層,就不再能保證每一對頂點按預期的次序看到所有路徑;這需要另外的證明,並可能得到不同的結果。
無負權圈的假設被用到兩次:它保證可達頂點對的有限最小值存在,並使原地計算全程保持 。它的作用不僅是拒絕帶負權邊的輸入。若圖中可能含有負權圈,就必須說明期望的結果是偵測負權圈、對不受影響的頂點對給出有限距離,還是對能到達並離開這類圈的頂點對給出 。這些輸出規格相互關聯但並不相同,相應的算法需要額外的證明。
無窮大的表示與成本度量
常見錯誤
(用有限的哨兵值代表無窮大)
數學上的 是一個特殊值,而不是普通整數。在程式碼中,帶保護的加法可以在任一加數為無窮時返回無窮。若使用一個固定的很大哨兵值,再加上負權邊的權重,就可能得到誤導性的有限值,除非溢出和所有有限距離的界都得到控制。精確實數下的遞推式不存在這一表示問題;而具體實作必須明確處理它。例如,以 代表無窮大。若 不能到達 ,而邊 的權重為 ,則候選值 小於 ,於是一個不可達的頂點對被賦予一個有限的距離。
的計數把有限邊權的加法和比較視為單位運算。若有理數權重以二進制編碼,還必須考慮其精確算術成本和位元長度。即使原圖的邊很少,該方法也要儲存一個稠密的 表;重複運行單源算法,在資源上可能有不同的取捨。該定理並不聲稱稠密的全源表總是最高效的表示。
當 且沒有負權自環時,初始化給出 的表 ,唯一的階段不改變它。對於不連通的圖,一些元素保持無窮,另一些元素是有限的。這些情況都屬於同一個不變量;不會在各連通分量之間引入人為的路徑。
檢驗結果
一個有限的表項可以由具有該權重的一條顯式途徑支撐,這給出最短距離的一個上界。要證明該表項同時也是下界,則需要依靠動態規劃的不變量,它考慮了每一個容許的中間頂點。僅僅找到一條較短的途徑,並不足以證明不存在更短的途徑。反過來,一個不可達的表項需要可達性論證,而不是對少數幾條候選路徑的搜尋未果。
在三頂點的例子中,由 到 的表項有見證 ,權重為 。由 到 的表項有見證 ,權重為 。完整的遞推式確立了不存在更便宜的途徑。見證有助於發現算術錯誤,但不能取代遞推式的證明。
總結
狀態 把內部頂點限制在前 個頂點之內。最短路徑要麼在內部不經過 ,要麼在 處被拆開。在沒有負權圈時,第 行和第 列在該階段保持不變,從而容許標準的原地三次方算法。
練習
快速檢查
(若 ,,,則 是多少?)
把舊值與經過 的和作比較。
解答 · 答案
它等於 。
快速檢查
(對於之間沒有任何有向途徑的頂點對,用甚麼值表示?)
考慮根本沒有途徑的情形。
解答 · 答案
該值為 。
快速檢查
(為甚麼零長度途徑令每個初始對角線元素至多為零?)
數一數沒有邊的途徑。
解答 · 答案
由某頂點到其自身的零長度途徑權重為零;在沒有負權圈時,不存在權重更小的閉途徑,所以對角線恰好為零。
快速檢查
(一條負權邊是否必然產生負權圈?)
考慮只有一條邊的圖。
解答 · 答案
不一定。若圖中只有一條權重為 的有向邊且沒有返回路徑,則圖中根本沒有圈。