動機
多種圖算法都反覆選取頂點或邊,但證明保護的意義不同。廣度優先搜尋確定按邊數計的距離;最小生成樹最小化連接所有頂點的總成本;Dijkstra 算法確定從源點出發的距離。混淆這些目標,可能得到看似合理、實際卻解了另一問題的算法。
本篇使用有限簡單圖,頂點集 、邊集 ,以鄰接表表示。有向邊為有序對,無向邊在兩端各檢查一次。路徑不重複頂點,遊走則容許重複。加權結論假設精確實數加法及比較為單位成本;長整數或有限精度須另作分析。記 。
定義
定義 3.2.1
(遍歷與距離)
若從源點 存在遵從方向的有向路徑到某頂點,便稱該頂點可達。無向邊可向任一方向走。無權距離是這種路徑的最少邊數,不可達者為無窮。加權距離取源點到該頂點的全部遊走權重之下確界;無遊走時為正無窮,權重無下界時為負無窮。可達負環可能使相關可達頂點的距離成為負無窮。
定義 3.2.2
(樹、割與鬆弛)
連通無向圖的生成樹是包含全部頂點、連通且無環的子圖。最小生成樹(MST)在所有生成樹中總邊權最小。割把頂點分成一個非空子集與其非空補集;端點分處兩邊的邊稱為跨割邊。鬆弛有向邊 ,指把暫定距離 改為 ;若 無窮則忽略。
連通無環圖中每對頂點有唯一路徑,因為兩條不同路徑會形成環。刪去樹邊會使它斷開;加入新邊則恰產生由該邊及原有唯一路徑構成的一個環。這些基本事實支持後面的交換證明。權重相同時 MST 未必唯一,且 MST 問題容許負權。
定理 / 命題
定理 3.2.3
(遍歷保證)
廣度優先搜尋(BFS)在首次入隊時標記頂點,使用先進先出隊列。源點距離為零,初次發現鄰點時設其距離為當前頂點距離加一。所得距離是真正無權最短距離,並在 時間找出全部可達頂點。
深度優先搜尋(DFS)在完成當前頂點前,先遞歸探索每個未訪鄰點。完整 DFS 森林需 時間。有向無環圖中,把完成次序倒轉便得拓撲排序,即每條邊均指向次序較後者。
定理 3.2.4
(割交換與 Kruskal 算法)
若森林 包含於某 MST,且某割沒有 中的跨割邊,則跨割的最輕邊可加入 ,同時仍包含於某 MST。因此 Kruskal 算法按非遞減權重掃描邊,只在兩端屬不同當前分量時接受,會在連通無向圖構造 MST。
定理 3.2.5
(Dijkstra 的確定規則)
若全部邊權非負,初始化 、其餘無窮;每次確定未處理頂點中有限暫定距離最小者,並鬆弛其出邊。每個確定值都是真正最短距離。當再無有限未確定值,其餘頂點均不可達。
定理 3.2.6
(含負邊的 Bellman–Ford 算法)
設從 不可達任何負環。則在對每條邊鬆弛的 輪之後,標號等於真實距離,所需時間為 。再多做一輪後仍能降低某個標號,當且僅當從 可達一個負環。
證明思路或證明
證明
(BFS 依距離次序發現頂點)
BFS 記錄實際路徑:新頂點的路徑是在當前路徑後接一邊。隊列按非遞減距離處理頂點。最初只有距離零;處理距離 頂點時,只會在現有隊列後加入距離 者,而原隊列的距離為 或 ,歸納得次序性。若某頂點初次距離大於真正最短值,在一條最短路徑上取首個未得到正確距離的頂點。其前驅已有正確的較小距離,會在任何能給出較長發現路徑的頂點前處理,從而以正確距離發現該點,矛盾。可達性亦由路徑上首個未發現頂點證明:其已發現前驅終會檢查相應邊。
入隊時標記保證每頂點至多入隊一次,每個鄰接項檢查一次,加上初始化即得所述時間,包括非連通輸入。前驅指標可重建最短路徑,在可達頂點上形成發現樹。對加權圖使用 BFS 仍只最小化邊數,未必最小化總權重。
DFS 完成時間證明甚麼
證明
(反向完成次序是拓撲排序)
使用三色:發現前白色,遞歸堆疊中灰色,完成後黑色。有向邊指向灰色鄰點時,該鄰點是活躍堆疊中的祖先,堆疊路徑加這條邊便構成有向環。有向無環圖不可能出現這情況。考慮邊 :檢查時若 白色,它將遞歸完成後才完成 ;若黑色,它已完成;灰色不可能。因此每條邊的 都比 早完成,倒轉完成次序便拓撲有序。
對每個剩餘白色頂點再啟動 DFS,可覆蓋非連通圖與全部有向分量。每頂點只經一次各色轉換,每個鄰接項只檢查一次,所以線性。無向圖偵測環須另外處理回到父點的邊,不能不加條件複製有向灰邊判據。
反例模式
無向圖中的灰色鄰點
考慮這樣的說法:在無向圖中,DFS 遇到灰色鄰點就證明存在環。取只有一條邊 的圖,從 開始 DFS。它發現 ,而從 考察通向 的邊時, 是灰色的。所謂的環是 ,但這個圖根本沒有環。回到父頂點的邊就是同一條無向邊,不是第二條邊。對簡單無向圖,修正後的判據要忽略指向父頂點的樹邊:不是父頂點的灰色鄰點,經由另一條邊到達,才說明存在環。
MST 的交換
證明
(最輕的跨割邊是安全的)
取包含 的 MST , 為跨割最輕邊。若 ,已完成;否則把 加入 產生唯一環。原來連接兩端的路徑也跨過此割,所以環含另一跨割邊 。由 無跨割邊,。刪 恢復生成樹並包含 。由 ,新樹權重不大於最優的 ,故亦最優。平手時也成立。
證明透視
被換出的邊為何存在而且無害
交換是一次只換一條邊的操作,依賴兩個關於割的事實。把 加入樹中會形成一個經過 的環,而與割只相交一次的環必定再次穿過該割,所以邊 存在。由於 中沒有邊跨越這個割,,所以刪去 之後,新樹仍包含 。不等式 是用到「最輕」的唯一之處,它使新樹不會更重。若去掉對 的條件,就可能 ,交換會破壞包含關係;若去掉最輕的條件,就可能 ,樹可能變重。只需要 ,所以權重相同並無妨礙。
證明
(Kruskal 算法構造 MST)
Kruskal 起初空森林包含於某 MST。對每條接受邊,取其某端的當前分量形成割;已接受邊均不跨割。此邊跨割最輕,因為更輕跨割邊早已處理,而且其兩端現在仍不同分量,當時也必不同,應已被接受。因此安全邊命題保持不變量。每次接受都合併分量而不產生環。若掃完仍有多個分量,連通性會給出一條應被接受的分量間邊,矛盾。最後森林遂連通且為 MST。
實作分量時,無需假設複雜攤銷定理:用父指標樹,把較小分量的根接到較大分量根之下。每當某頂點深度增加,其分量大小至少加倍,故深度至多 。每條邊的找根與合併需 。排序需 ;簡單圖有 ,故總時間 ,空間 。路徑壓縮改進不在此證明內。
Dijkstra 為何需要非負邊
證明
(Dijkstra 確定的是真實距離)
每個有限暫定距離都是某實際源點遊走的權重,所以在最優值存在時不小於它。非負權允許移除環而不增加成本,因此每個可達頂點都有最短路徑。假設先前確定均正確,取下一選定頂點 。在到 的最短路徑上,取首個未確定頂點 。若 ,暫定值為零;否則其前驅 已確定,鬆弛 已令 不大於到 的最短路徑前綴權重。最短路徑前綴也最優,否則替換較好前綴會改善整條遊走,再刪環即可改善路徑。
非負性保證此前綴權重不大於到 的完整距離。最小選取規則給 ;實際遊走性質給反向不等式,故確定正確。若尚有可達頂點而所有未確定值均無窮,取可達路徑上首個未確定點,其已確定前驅應給它有限值,矛盾。
證明透視
路徑上第一個未確定的頂點
證明不能直接把 與它在最短路徑上的前驅相比,因為那個前驅本身可能尚未確定。關鍵的一步是選取 ,即路徑上第一個未確定的頂點。它的前驅已確定,所以鬆弛已經使 不超過該路徑前綴的權重。非負性只使用一次:說明這個前綴不會比整條路徑更重,得到 。若 之後有負邊,整條路徑可能比前綴更輕,這個不等式就不成立。對 的最小選取給出 ,而「每個有限標號都是實際遊走的權重」給出 。
每次掃描未確定頂點找最小,時間為 ,鄰接表以外距離及前驅空間為 。二元堆可改善界,但須另證操作成本;距離不變量的正確性不依賴優先隊列實作。距離與前驅也不同:零權平手時應有一致更新規則,避免相同值替換造成前驅環。
負邊與 Bellman–Ford
證明
(Bellman–Ford 求出距離並檢測負環)
負邊破壞 Dijkstra 的前綴不等式,但可改為限制遊走邊數。令 為最多用 邊到 的最小遊走權重,,其餘初值無窮。則
方案已窮盡:遊走或最多用 邊,或有最後一邊且前綴最多用 邊。反之,每個有限候選值都能接邊實現。若無從 可達的負環,刪去環不增加成本,最優路徑最多用 邊,故 給出全部距離。
通常原地 Bellman–Ford 初始化後,作 輪,每輪鬆弛所有邊。第 輪後的值不大於 ,因為每輪內值只減少,可用歸納證明;它們仍是實際遊走權重。因此沒有可達負環時, 輪後恰等於真正距離。時間 ,輔助空間 。直接用兩行計算上述式子也正確,但每輪複製全部頂點時時間為 ;其中間行未必等於原地算法的中間值。
若額外一輪仍可減少有限距離,便偵測到可達負環。若無此環,距離已精確,不可能再降。反之,若無邊可下降,沿可達環把 相加,便得環權重非負;可達性傳播後其全部頂點標號都有限。因此可達負環必迫使某個進一步下降。單源初始化不偵測不可達負環,而它們也不影響該源點的距離。
例題詳解
例題 3.2.7
(有向圖的 BFS 層)
邊為 。BFS 層為 ,距離依次零、一、二、三。視鄰接次序而定, 或 都可能成為 的前驅。距離唯一,選出的最短路徑卻未必唯一。
例題 3.2.8
(生成樹不是最短路徑樹)
無向三角形取 。MST 用 ,總重四,其樹上 到 路徑重四,但圖中最短路線是重三的 。以 為根的最短路徑樹用 ,總重五。兩棵樹各自優化其指定目標。
反例模式
沒有負環並不足以使用 Dijkstra
考慮這樣的說法:只要圖中沒有負環,Dijkstra 的確定規則就仍然正確。取有向邊 權重為二, 權重為五, 權重為負四。Dijkstra 在考察 之前就以 確定 ,因為 。路徑 的權重為 ,所以到 的真實距離是一。這個圖完全沒有環。該規則需要每條邊的權重各自非負;而不提前確定任何頂點的 Bellman–Ford 算法會得到值一。
例題 3.2.9
(含不可達頂點的 Dijkstra)
設有向邊為 權重 , 權重 , 權重 ,且 沒有入邊。起初 ,其餘標號為無窮。確定 並鬆弛,得 、。確定最小有限標號的 ,並鬆弛 ,得 。確定標號為 的 之後,只剩下標號為無窮的 ,規則於是停止。各距離為 。通向 的直接邊並不是最短的,而不可達的頂點 保持 。
概念視角結構
三種選擇,三種保證
BFS 選隊首頂點,確立邊數層;Kruskal 選邊,確立仍可延伸到全局最優生成樹;Dijkstra 選最小標號,確立該標號不會再改善。選取形式相似,但保證及假設不同;MST 交換不能替代最短路徑確定證明。
常見錯誤
常見錯誤
(先確認問題,再選算法)
先確認圖是否有向、關心全部頂點還是單源、權重可否為負。非連通無向圖沒有生成樹,Kruskal 只產生各分量的最小生成森林。DFS 樹路徑一般非最短。向部分森林加邊安全,是因為割證明,不能只因邊便宜。
常見錯誤
(表示方式與哨兵值)
複雜度依賴表示及數據結構。鄰接矩陣需二次空間,與稀疏鄰接表不同。最短路徑還須區分無窮與很大的有限數;數學證明未保證某個可能溢出或與真正距離混淆的哨兵值安全。
總結
遍歷不變量建立可達性、層及完成時間次序。MST 的割交換保持可延伸至最優解。Dijkstra 靠非負權確定最小標號,Bellman–Ford 則用反覆鬆弛及明確負環偵測。指出各自保護的保證,可分清及檢驗外表相近的圖程序。
練習
快速檢查
(給有向圖,使 DFS 因鄰接次序而首次找到比最短路徑長的路徑。)
讓 既有指向目標的直接邊,又有一條較長的路線。
解答 · 答案
用邊 ,並從 先探索 再探索 。DFS 首次沿三條邊到達 ,而直接邊的長度為一。這條發現路徑有效,但並非最短。
快速檢查
(解釋為何用任意非最輕跨割邊取代最輕邊會破壞 MST 證明,並給加權三角形例。)
交換用到哪一個不等式?
解答 · 答案
交換需要 ,這樣交換才不會增加樹的權重。取三角形,,,,並取割 對 。邊 跨越該割但不是最輕的,因為 也跨越該割且權重為一。每棵含 的生成樹還含 或 ,所以權重至少為 ,而最小生成樹 的權重為三。因此 不是安全邊。
快速檢查
(邊 權四、 權五、 權負二。計算 及真正距離。)
每一行都按 的次序書寫。
解答 · 答案
按 次序,,,,因為 。圖中沒有環,最後一行就是真正距離。若原地的一輪先考察 再考察 ,第一輪就可能得到二,這說明它的中間陣列不必等於同步的各行。
練習 3.2.10
(證明有限有向圖有拓撲排序,當且僅當它沒有有向環。)
核心證明
可使用上面證明過的 DFS 三色論證。
解答(3)
- 1
排序排除有環
沿著一個有向環,相鄰頂點的位置會嚴格遞增並回到起點,這是不可能的。
依據: 在拓撲排序中,每條邊都嚴格增加位置。
- 2
無環排除灰色鄰點
關鍵一步
若在無環圖上,DFS 從 遇到灰色鄰點 ,則堆疊上從 到 的路徑加上邊 就是一個有向環。
依據: 灰色鄰點會與堆疊上的路徑構成環。
- 3
反向完成次序是拓撲排序
∎對 DFS 考察的邊 , 若是白色,就會先於 完成;若 已是黑色,則早已完成。所以 先於 完成,於是在反向完成次序中 排在 之前。每條邊都如此,所以這個次序是拓撲排序。