一個圖可以支持若干不同的問題。哪些頂點可達?最短路線使用多少條邊?一條路線的最小總邊權是多少?哪些邊能以最低成本把整個網絡連通?圖形相似並不表示這些問題可以互換。要理解相應的算法,最好的辦法是為每一個前沿、每一個距離標號和每一條被選中的邊賦予精確的含義。
動機
試想頂點是地點,邊是容許的移動。當每次移動的成本相同時,按發現次序處理頂點,自然會依次顯示愈來愈長的路線長度。當成本不同時,單憑發現次序就不足夠了:一條昂貴的單邊路線可能輸給一條便宜的多邊路線。此時必須以優先規則來追蹤暫定的總成本。
生成樹問題再次改變了目標。它對一組邊只付一次費用,使所有頂點連通起來,而不是使每位出行者到選定源點的距離最小。建造成本最低的網絡,可能迫使某些頂點之間的行程更長。說明這一區別,可以避免把最短路徑算法誤用為最小生成樹算法這個常見錯誤。
這三個問題都可以從前沿的角度來看。BFS 把已處理的層與尚未發現的頂點分開。Dijkstra 把距離已經最終確定的頂點與只有暫定標號的頂點分開。生成樹算法則把各個連通分量或一棵不斷生長的樹與其餘部分分開。不同之處在於:如何證明以所提出的方式越過前沿是安全的。
定義
定義 4.5.1
(途徑、路徑與可達性)
有限有向圖具有頂點集 和有向邊集 。無向邊在不指定方向的情況下連接兩個頂點;在遍歷時,它可以用兩個有向關聯來表示。途徑(walk)沿著相連的邊前進,可以重複經過頂點。路徑(path)指沒有重複頂點的途徑。若存在從 到某頂點的途徑,則稱該頂點從 可達;當可達性成立時,刪去重複的閉合部分即可得到一條路徑。
定義 4.5.2
(無權距離與 BFS)
在無權圖中,距離 是從 到 的途徑所含邊數的最小值;若不存在這樣的途徑,則為無窮大。BFS 使用先進先出的隊列。它令 ,把 標記為已發現,然後反覆取出隊列最前面的頂點 。每個尚未被發現的鄰點 即時被標記,賦予 和父節點 ,並加入隊列末端。
定義 4.5.3
(帶權距離與 Dijkstra 算法)
對於帶權圖,一條途徑的權是其各邊權之和。Dijkstra 算法假設每條邊的權都是非負的。它初始化 ,其餘標號為無窮大。算法反覆選取一個標號有限且最小的未確定頂點,將其確定,並鬆弛它的出邊:若 ,則替換後者的標號並記錄父節點 。當不再有標號有限的未確定頂點時停止。帶權距離 是從 到 的途徑的權的最小值;若不存在這樣的途徑,則為無窮大。
定義 4.5.4
(生成樹、最小生成樹與割)
對於連通的無向圖,生成樹是包含所有頂點的連通無環子圖,它有 條邊。最小生成樹(minimum spanning tree,簡稱 MST)使其邊權之和最小。MST 的邊權可以為負:與最短途徑不同,樹不能重複經過負環。圖的割是把頂點劃分為兩個非空部分。若一條邊的兩個端點分屬不同部分,則稱該邊橫跨此割;若邊集中沒有邊橫跨該割,則稱該邊集與此割相容。
定理/命題
定理 4.5.5
(BFS 計算無權距離)
在以鄰接表表示的有限圖中,BFS 恰好發現從源點可達的那些頂點,並為每個頂點賦予其最小邊數距離。每個頂點至多入隊一次,包括初始化在內的運行時間為 。
定理 4.5.6
(Dijkstra 算法中已確定的標號是最終的)
對於邊權非負的有限有向圖或無向圖,Dijkstra 算法所確定的每個頂點都滿足 ,其中 為帶權距離。算法終止時仍為無窮大的頂點是不可達的。
定理 4.5.7
(最小生成樹的割性質)
設 為連通的有限無向帶權圖, 為包含於某棵 MST 的邊集。取定一個割,即把頂點劃分為兩個非空部分,且 中沒有邊橫跨該割。若 是橫跨該割的權最小的邊,則存在一棵包含 的 MST。特別地,橫跨割的最輕邊屬於某棵 MST,但在出現權相等的情形時,它不一定屬於每一棵 MST。
在安全邊的表述中,「先前的選擇」被假定包含於至少一棵 MST,而且割必須與它們相容,即其中沒有邊橫跨該割。在算法中反覆使用割性質時,必須明確這一不變量。
證明思路或證明
證明
(BFS 標號等於距離)
BFS 隊列中的標號從隊首到隊尾是非遞減的:處理一個標號為 的頂點,至多只會在當前隊列中所有標號為 的頂點之後追加標號為 的頂點。每個被賦予的標號都由其父節點鏈實現,因此不會小於真實距離。反之,取一個真實距離為 的頂點及到它的一條最短路徑。其前驅的距離為 ,由對 的歸納,它被處理時帶有正確的標號。該頂點要麼已被發現且標號至多為 ,要麼此時被發現並獲得標號 。結合由路徑實現的不等式,便得到等式。可達頂點都出現在某個有限的路徑長度上,所以歸納法保證它們全部被發現;不可達頂點不可能獲得從 出發的父節點鏈。
證明
(被選中的標號已經精確)
對於 Dijkstra 算法,每個有限標號都是某條源點途徑的權,所以 。假設所有先前已確定的標號都是正確的,並設 是下一個被選中的頂點。在到 的一條最短路徑上,令 為第一個未確定的頂點,其前一個頂點 已確定;若在初始步驟中 ,則另當別論。從 出發的鬆弛給出 ,因此等式成立。其餘各邊非負,給出 。所選標號的最小性給出
因此所有不等式都是等式, 被正確確定。源點是歸納的起點。每個可達頂點都存在最短路徑:在權非負時,去掉迴圈不會增加權,所以最小值可以在有限多條簡單路徑中取得。若某個可達頂點仍為無窮大,則一條路徑上第一個未被發現的頂點會從其已確定的前驅得到一次有限的鬆弛,這與算法終止矛盾。
證明透視
非負性在哪一步起作用
兩個不等式確定一個已確定標號。容易的一個是 ,因為有限標號是某條真實途徑的權。困難的一個是 ,它來自到 的一條最短路徑上第一個未確定的頂點 :取第一個未確定頂點,就保證它之前的頂點都已確定,所以 是由正確標號鬆弛而得,;又因 在未確定頂點中標號最小,故 。非負性恰好只在鏈中的一環起作用,即 :從 到 的其餘路徑不可以有負權。在下面的負邊反例中, 先被選中,它的最短路徑上第一個未確定的頂點是 ,這一環便失效:。
證明
(以最輕的橫跨邊交換較重的橫跨邊)
對於割性質,先取一棵包含先前選擇的 MST。若它含有所提出的橫跨邊 ,則無需再做甚麼。否則,加入 會產生唯一一個圈:原樹在 的兩個端點之間已有唯一一條路徑。這條路徑橫跨該割,所以該圈含有另一條橫跨邊 。因為割與所有先前的選擇相容, 不是其中之一。刪去 ,得到的是一棵保留先前選擇並含有 的生成樹。由於 是橫跨邊中最輕的,,所以新樹的權不大於原樹。由最小性,它是一棵 MST。這是一個交換論證,其可行性由圈的替換來保證。
Prim 算法從一個頂點出發,反覆選取從其不斷擴大的頂點集通向外部的最小權邊。其割與所有先前選中的邊相容,所以割性質保持了「已選森林可擴展為一棵 MST」這一不變量。Kruskal 算法按權由小到大處理各條邊,僅當一條邊的兩個端點屬於當前不同的分量時才加入它。對於被加入的邊,把其中一個分量與其餘部分分開的割是相容的,而且在不同分量之間不可能有更輕的橫跨邊曾被拒絕。同一個不變量即可證明其正確性。每次成功加入一條邊都會使分量數減少,所以對連通的輸入,最終得到一棵生成樹。
例題詳解
例題 4.5.8
(按邊數與按權計算的距離)
考慮無向圖,其邊為 、、、、、、、。從 出發的 BFS 給 賦距離零,給 賦距離一,給 賦距離二。Dijkstra 則按 的次序確定頂點,帶權距離依次為 。到 的最便宜路線是 ,使用四條邊。存在一條兩條邊的路線,但其權為十一,所以對 BFS 自身的目標而言正確的答案,並不是帶權最短路線。
例題 4.5.9
(最短路徑樹不一定是 MST)
取三個頂點,邊權為 、、。以 為根的最短路徑樹使用兩條源點邊,總邊權為四。MST 使用 和任一條源點邊,總權為三。在該 MST 中,源點到某個頂點的距離變成三,而不是最優的二。使建造成本最小與使源點距離最小,對同一個圖提出了不同的要求。
例題 4.5.10
(帶權圖上的 Kruskal 算法與被拒絕的邊)
在第一個例題的圖上,把邊排序:、、、、、、、。取 :它連接分量 與 。取 :它連接 與 ;兩條權為一的邊互不相交,所以先後次序不影響結果。取 :它把 與 連起來。把 與其餘頂點分開的割,被 、、 和 橫跨,而 最輕,正符合割性質的要求。取 :它把 併入其餘部分,此時森林有 條邊,總權為 。其餘的邊 、、、 的兩個端點都在唯一的分量內,加入會形成圈,所以 Kruskal 算法拒絕它們。被拒絕的邊就是邊界情形:只要端點已經連通,不論邊的權是多少,這條邊都會被捨棄。
反例模式
負邊使永久確定失效
一個看似合理的說法是:只要圖中沒有負環,Dijkstra 的規則就能給出正確的距離。取有向圖: 的權為二, 的權為五, 的權為負四。它完全沒有圈。第一輪鬆弛後的標號是 、,所以 Dijkstra 確定 ,標號為二。接著它確定 ;鬆弛 本會給出 ,但 已經確定。途徑 的權為一,所以 。修正的辦法是對這種確定規則要求邊權非負。有負邊時,需要一個可以重新訪問已確定標號的過程,那就不再是上面所證明的算法了。
使用鄰接表時,BFS 對每條有向邊掃描一次(無向邊的每個關聯掃描兩次),對每個頂點掃描一次。Dijkstra 的簡單陣列實作透過掃描所有頂點來找出每個最小值,共需 次運算。使用二元堆並配合適當的減鍵(decrease-key)實作,對非平凡的圖需要 次運算。Kruskal 算法需要對邊排序並維護分量;即使是簡單的分量實作也是多項式時間的,而不相交集結構可以改進分量操作。這些成本假定對邊權的比較和算術運算的成本為常數。編碼很長的精確有理數權,則需要另行作位元成本分析。
常見錯誤
常見錯誤
(只在出隊時才標記 BFS 的頂點)
若要使用「只入隊一次」的不變量,應當在入隊時而不是僅在出隊時標記 BFS 的頂點。否則,在某個頂點被處理之前,可能有多個鄰點把它重複入隊。這樣得到的過程也許仍可修復,但其狀態和成本證明都已改變。
常見錯誤
(把割的證明套用到不連通或有向的圖)
對於不連通的輸入,覆蓋所有頂點的 MST 並不存在;自然的類比是最小生成森林,每個連通分量一棵樹。有向圖中的最小成本連通問題也不同於無向 MST 問題。當有向可達性取代了無向連通性時,不要不加說明地套用割的證明。
常見錯誤
(以為最輕的邊必屬於每一棵 MST)
權相等可以產生多棵 MST。割性質保證的是存在一棵包含所選最輕邊的 MST,而不是在存在權相等的替代邊時該邊屬於每一棵 MST。在三邊權都是一的三角形中,任意兩條邊都是一棵 MST,所以每條邊都會被其中一棵 MST 捨去。如果某個割有唯一的最輕邊,則交換論證可以加強,證明它屬於每一棵 MST。
總結
BFS 使用層,因為每條邊貢獻一個單位。Dijkstra 使用暫定權重,並且需要邊權非負,才能最終確定前沿中的最小值。MST 算法最小化的是整個邊集的全局成本,並使用割與圈的交換。數據結構實作這些想法;而不變量則解釋了所得答案為何能解決所述問題。
練習
快速檢查
(求「按邊數與按權計算的距離」例題中五頂點圖的一棵 MST,並給出其總權。)
把邊排序,並跳過會形成圈的邊。
解答 · 答案
選取權為一的 、權為一的 、權為二的 和權為三的 。這些邊連通全部五個頂點且沒有圈,總權為七。每一步都套用割性質(如 Kruskal 例題所示),便保證了最小性。在這個例子中,所選的四條邊恰好也構成從 出發的帶權最短路徑樹,但第二個例題表明這種巧合並不具有一般性。
練習 4.5.11
(證明橫跨某個割的唯一最輕邊屬於每一棵 MST。)
核心證明
設 為連通的帶權無向圖, 是橫跨某個固定割的唯一權最小的邊。
解答(3)
- 1
假設某棵 MST 不含
是生成樹,所以在 的兩個端點之間有唯一一條路徑。把 加入 恰好產生一個圈。
- 2
在該圈上找出另一條橫跨邊
關鍵一步
這個圈含有橫跨該割的 ,所以還含有另一條橫跨邊 。因為 是唯一的最輕橫跨邊,。
依據: 圈橫跨一個割的次數是偶數。
- 3
交換兩條邊並與最小性矛盾
∎從唯一的圈中刪去一條邊,餘下的仍是生成樹,所以 是生成樹,且 。這與 的最小性矛盾,所以每棵 MST 都含有 。嚴格不等式正是權相等時所不具備的額外事實。
快速檢查
(解釋為甚麼當圖中所有邊的權都相同且為正時 BFS 是有效的,並說明如何由其輸出得到帶權距離。)
比較一條途徑的權與它所含的邊數。
解答 · 答案
若每條邊的權都是 ,則含 條邊的途徑的權為 ,所以最小化權等價於最小化邊數。把每個有限的 BFS 距離乘以 ;不可達的頂點仍為無窮大。 的情形很平凡:所有可達頂點的帶權距離都是零。
快速檢查
(在負邊的例題中,計算正確的距離,並指出 Dijkstra 歸納中恰好是哪一步失效。)
找出到 的真實最短路徑上第一個未確定的頂點。
解答 · 答案
距離為:到 為零,到 為五,到 為一。當 先於 被選取時,到 的真實最短路徑上第一個未確定的頂點是 ,其距離五大於最終的路徑成本一。因此後綴不等式 不成立,因為該路徑的最後一條邊權為負。