動機
沒有環的有向圖具有一種特殊的處理次序:每條邊都指向前方。一旦頂點按這種次序排好,最短路徑算法就可以在某個頂點的所有可能前驅都處理完之後,才確定該頂點的結果。由於之後的邊不可能再回到前面的頂點並修改其結果,所以容許出現負邊權。
本章證明兩部分內容:如何得到拓撲序或檢測出有向環,以及為甚麼按該次序對各邊作一遍鬆弛就能求得最短路徑。拓撲排序失敗,就是一份結構性證明,說明一遍掃描算法的前提不成立。
定義
定義 3.4.1
(拓撲序與 DAG)
設 為有限有向圖,有 個頂點和 條邊。拓撲序是對所有頂點的一種排列,使得每條邊 中 都排在 之前。有向無環圖簡稱 DAG。自環是一個有向環;平行邊是容許的,並且在計算入度時分別計數。
定義 3.4.2
(Kahn 算法)
Kahn 算法先計算各頂點的入度,把所有入度為零的頂點放入隊列,然後反覆取出一個隊列中的頂點並輸出。對於該頂點的每條出邊,算法將其頭部頂點的當前入度減一,當計數變為零時把該頭部頂點加入隊列。這些計數針對的是由尚未移除的頂點所導出的子圖。如果輸出的頂點少於 個,算法就報告存在環。
定義 3.4.3
(源點標號與鬆弛)
對於最短路徑,假設每條邊都有有限實數權重,並且給定了源點 。初始化 ,其餘所有標號為 。按拓撲序處理各頂點;對每條出邊 ,把 替換為 。約定 仍為 。
定理
定理 3.4.4
(拓撲排序與環)
有限有向圖存在拓撲序,當且僅當它無環。Kahn 算法在 DAG 上輸出這樣的拓撲序,否則報告存在環。
定理 3.4.5
(DAG 中的最短路徑)
在帶權 DAG 上,一遍拓撲鬆弛算法可以求出源點到各頂點的最短距離(不可達頂點的距離為 )。在圖以鄰接表表示之後,所需時間為 。
證明
證明:源點與隊列
證明
(DAG 必有源點,Kahn 算法輸出拓撲序)
有限非空的 DAG 必有入度為零的頂點。否則,從任一頂點出發,反覆沿一條入邊向後走。由於頂點只有有限個,必有某個頂點重複出現,重複的那一段就給出一個有向環。從 DAG 中移除一個入度為零的頂點,所得仍是 DAG,所以在無環圖中,只要還有頂點剩餘,Kahn 算法的隊列就不會變空。
當一個頂點被移除時,它的當前入度為零,因此它的所有前驅都已被移除。所以,對於完全輸出的圖,每條邊在輸出次序中都指向前方。反過來,含有有向環的圖不可能有拓撲序:沿著環上的邊走,要求環上每個頂點都排在下一個頂點之前,最終將要求某個頂點排在它自己之前。
證明
(提前停止會暴露一個環)
如果 Kahn 算法提前停止,則剩餘子圖非空,並且其中每個剩餘頂點在該子圖內的入度都為正。沿入邊向後走必然重複某個頂點,從而暴露出一個有向環。因此提前停止的判斷是正確的。未處理的集合中可能含有不在環上的頂點;證明所保證的是,其中至少包含一個環。
證明:拓撲鬆弛
證明
(拓撲鬆弛求出最短距離)
每個有限的暫定標號都是某條真實的源點到該頂點路徑的權重:初始時只有到 的空路徑,權重為零;而每次鬆弛都是在一條已被表示的路徑後追加一條邊。因此,沒有任何有限標號會小於真實的最短路徑距離。
按拓撲序考察各頂點。在處理頂點 之前,它的每個入鄰點都已被處理,所以它的每條入邊都已被鬆弛過。若 可達且不是 ,取一條到 的最短路徑,設 是該路徑上 的前驅。DAG 中的有向路徑不會重複頂點。該路徑到 的前綴是一條源點到 的最短路徑;否則,把這段前綴換成更短的路徑,就會得到一條到 的更短路徑。由歸納假設, 被處理時 已經正確,所以對 的鬆弛使 不超過最短距離。路徑見證不變量給出相反的不等式,因此兩者相等。
對於 ,空路徑的權重為零,並且在 DAG 中沒有有向路徑能回到 。從 不可達的頂點永遠得不到有限的路徑見證,因此保持為 。負權重不會給歸納帶來任何困難:保證每個相關前驅先被處理的是拓撲序,而不是「最小標號優先」的規則。
證明透視
為甚麼一遍掃描就足夠
歸納沿著拓撲序進行,而不是沿著距離的大小進行。無環性用了兩次:第一,它提供了次序,所以在處理 之前,進入 的每條邊都已被鬆弛;第二,它使每條路徑都是簡單路徑,所以到 的最短路徑存在,而且它到前驅的前綴仍是最短路徑。「每個有限標號都是某條真實路徑的權重」這一不變量使 恆成立,其中 是真實距離。某條最短路徑的最後一條邊在其尾部頂點定案之後被鬆弛,就給出 。權重的正負號在兩個不等式中都沒有出現,所以負邊是無害的。若沒有無環性,消失的是次序:在環上,沒有任何頂點可以排在它所有前驅之後處理。
時間與路徑重構
Kahn 算法通過掃描一遍所有邊來計算入度。每個頂點至多入隊和移除一次,每條邊在其尾部頂點被移除時被掃描一次。使用鄰接表時,其時間和空間均為 。鬆弛過程同樣對每個頂點和每條邊各掃描一次,因此包括拓撲排序在內,總時間為 。
每當 被嚴格改進時,記錄 以及邊 作為前驅。對於可達且 的頂點,沿前驅回溯會在拓撲序中不斷向前移動,因此一定會終止於 。把所記錄的邊反向排列,就得到一條最短路徑。當成本相等時保留已有的前驅,可以避免不必要的改動;如果需要精確的邊序列,則應當分別標識各條平行邊。
例題詳解
例題 3.4.6
(負邊是無害的)
設有三條邊: 權重為二, 權重為五, 權重為 。按次序 ,處理 時得到 與 。處理 時把 改進為 。之所以容許出現負邊,是因為該圖是無環的。
例題 3.4.7
(源點不必排在第一位)
若 是一條邊,但 從 不可達,則拓撲序可以把 排在 之前。它的標號保持為 ,所以鬆弛它的出邊不會改變 。源點不必是拓撲序中的第一個頂點。
例題 3.4.8
(環阻礙了拓撲序)
對於邊 、 和 ,每個頂點的入度都為正。Kahn 算法的初始隊列為空,沒有任何頂點被輸出。這三條邊構成一個有向環,所以不存在拓撲序。
例題 3.4.9
(入度為零的並列情形)
對於邊 和 , 與 的初始入度都為零,可以先移除其中任何一個。 與 都是合法的拓撲序;算法並不要求拓撲序唯一。
常見錯誤
反例模式
負邊並不總是需要多遍掃描
在上述無環例子中, 的權重為 ,但一遍拓撲掃描就得到了正確的值 。Dijkstra 算法對非負權重的要求,源於它按最小標號確定頂點的證明;DAG 則提供了另一種次序,即使有負邊,這種次序仍然有效。
常見錯誤
(提前停止並不表示所有剩餘頂點都在環上)
Kahn 算法提前停止,證明的是剩餘子圖含有環,而不是每個未處理的頂點都在某個環上。位於環下游的頂點可能保持未處理,但它本身並不屬於任何環。
反例模式
按非拓撲序進行鬆弛
考慮這樣的說法:只要每個頂點處理一次,一遍鬆弛在任何 DAG 上都是正確的,不論採用甚麼次序。取邊 權重為 , 權重為 , 權重為 , 權重為 ,並按次序 處理各頂點。處理 得 、。處理 得 。處理 把 降為 ,但 已經處理過,所以 仍為 。處理 沒有任何變化。真實距離是 。次序 把 排在它的前驅 之前,所以不是拓撲序。在拓撲序 之下,標號依次成為 、、。修正後的說法需要拓撲序,使每個頂點都在它所有前驅之後處理。
常見錯誤
(次序取決於邊,而不是權重)
拓撲序是有向圖本身的性質,與邊權無關。改變權重不會令拓撲序失效,而加入一條反向邊則可能產生環,使拓撲序不再成立。例如 是路徑 的拓撲序,但加入邊 之後就不存在任何拓撲序。
提前停止後提取一個明確的環
如果 Kahn 算法的隊列變空而仍有頂點剩餘,就為每個剩餘頂點選定一條剩餘的入邊。這是可以做到的,因為每個剩餘頂點的入度都為正。從任一剩餘頂點出發,反覆沿所選的入邊向後走,並記錄每個頂點第一次出現的位置。至多經過 次訪問,必然出現重複。
按所記錄的邊的正向讀取,重複的那一段就是一個有向環。例如,反向遍歷可能依次訪問 ,所用的邊為 、 和 ;把這些邊按正向讀出,就是 。自環是長度為一的環。為每個頂點找出一條剩餘入邊,可以在提前停止後通過掃描原始邊表完成,所以提取環仍然只需 時間。
環下游的頂點說明了為甚麼整個未處理集合不能充當環的證明。在環 上加一條邊 。初始時沒有任何頂點的入度為零,所以四個頂點全部留下。如果 沒有出邊,它就不在任何有向環上,但剩餘子圖含有由 構成的環。
DAG 中的最長路徑
同一個拓撲序也可以用來計算 DAG 中的最長路徑權重。初始化 ,其餘標號為 ,然後在處理出邊時,把頭部標號替換為 。每個有限標號都是某條路徑的權重,同樣的前驅歸納法在不等號反向後證明其最優性。不可達頂點以 作為哨兵值保持不變。
DAG 只有有限多條有向路徑,所以即使某些邊的權重為正,可達的最長路徑也存在。這一結論不能原樣推廣到任意圖:若存在一個可達的正權環,並且該環能到達目標頂點,則存在權重無界的遊走。如果問題要求的是有環圖中的最長簡單路徑,則禁止重複頂點會改變問題本身,DAG 上的一遍掃描證明不再適用。
對於邊 權重為二、 權重為五、 權重為 ,到 的最長距離為五,而最短距離為 。這兩種算法使用同一個拓撲序,但更新運算相反。不可達標號也必須使用正確的哨兵:求最小值時用 ,求最大值時用 。
並列、多重邊與算術運算
一個圖可以有許多種拓撲序。每一步都可以選取任一入度為零的頂點,正確性證明對所有選擇都成立。如果有多條最短路徑權重相同,不同次序得到的前驅路徑可能不同,但每個報告出來的有限距離都是同一個最優值。
存在平行邊時,入度計數要包括每一條邊的副本。移除它們共同的尾部頂點時,頭部頂點的入度對每個副本各減一次,而鬆弛時則分別檢查每個權重。如果把兩個副本只算作一次入度貢獻,卻減了兩次,隊列的記賬就可能出錯。自環使其所在頂點的入度永遠不能降為零,因此會被正確地識別為環。
線性時間的結論假設對邊權和標號的算術運算與比較都是精確的。對於有限精度或任意精度的權重,這些運算的成本和可靠性取決於具體表示方式。圖論上的不變量不變,但其數值實作需要另行分析。特別地,有限數值的哨兵值在加上邊權時不能溢出,也不能與合法的有限路徑值混淆。
總結
DAG 總有入度為零的頂點,所以 Kahn 算法反覆移除這樣的頂點,就得到拓撲序。按此次序,所有入邊的鬆弛都發生在頂點被處理之前,因此即使有負權重,也能在線性時間內求出最短路徑。
練習
快速檢查
(給出邊 和 的一個拓撲序。)
一開始哪些頂點的入度為零?
解答 · 答案
或 都是合法的。 與 的初始入度都為零,而 必須排在兩者之後。
快速檢查
(在負邊的例子中,計算從 到 的距離。)
比較直接的邊與經過 的路徑。
解答 · 答案
路徑 的權重為 ,小於權重為五的直接邊。最短距離為 。
快速檢查
(為甚麼有限非空的 DAG 必有入度為零的頂點?)
沿入邊向後走。
解答 · 答案
否則每個頂點都有入邊,從任一頂點出發反覆沿入邊向後走,在有限圖中最終會重複某個頂點,重複的那一段是有向環,與無環矛盾。
快速檢查
(Kahn 算法提前停止後,能否認為每個未處理的頂點都在某個環上?)
想一想只從環接收一條邊的頂點。
解答 · 答案
不能。位於環下游的頂點,即使不在任何環上,也可能因入度為正而留下。只能保證剩餘子圖至少含有一個環。