先修:圖的表示、DFS 和 BFS。
廣度優先搜尋(BFS)通常只為每個頂點記錄一個父頂點。這足以還原一條最短路徑,卻會丟掉其他同樣短的路線。要計算所有最短路徑,我們同時維護距離和路徑數;當另一條邊進入已發現的頂點時,根據它所在的層數分別處理。
本單元將 BFS 擴展至單位邊長最短路徑計數。
1. 明確計算對象
設 是有限有向圖,頂點互不相同,不含平行邊,每條邊的長度均為 1。對於無向圖,只要鄰接表把每條邊按兩個方向各記一次,同一算法也適用。我們按頂點序列區分路徑。由於每條邊長都是 1,最短途徑不可能重複頂點:刪去非空圈會使它變短。因此在這裏,計算最短途徑與計算最短簡單路徑的結果相同。
定義
(距離與最短路徑數)
對源點 ,定義 dist[v] 為由 到 的最少邊數,不可達時為無窮大。定義 ways[v] 為達到該距離的路徑數。從 到自身恰有一條零邊路徑,因此 dist[s] = 0、ways[s] = 1;不可達頂點的路徑數為零。
我們假設非負整數運算精確、使用先進先出隊列,並透過鄰接表存取圖。如果圖允許平行邊,且按邊的選擇區分路徑,就掃描每次出現的邊並分別計數。如果路徑按頂點序列區分,則必須先去除重複鄰居;悄悄更改約定會改變答案。
2. 一個隊列,兩種情況
對每個 v:dist[v] = infinity;ways[v] = 0
dist[s] = 0;ways[s] = 1
queue = [s]
當 queue 非空:
u = pop_front(queue)
對 u 的每個鄰居 v:
如果 dist[v] == infinity:
dist[v] = dist[u] + 1
ways[v] = ways[u]
push_back(queue, v)
否則如果 dist[v] == dist[u] + 1:
ways[v] = ways[v] + ways[u]
返回 dist, ways
首次發現 v 時,每條到 u 的最短路線都可以接上 u -> v,形成對 v 的第一份貢獻。若 v 已被發現,且距離恰為 dist[u]+1,新貢獻來自另一個最後前驅,必須加上。若 dist[v] 較小,這次延伸太長,不應貢獻路徑數。這個相等條件避免較長路線令計數虛增。
只有首次發現時才將 v 加入隊列。這樣做是安全的,因為先進先出 BFS 按距離非遞減順序處理頂點:移出任何第 層頂點之前,第 層的所有頂點都已移出。因此移出 u 時,所有可能作為到 u 最短路徑末端前驅的頂點都已提供貢獻。用於出邊的計數已經完整。如果只在出列時標記,或每次收到等距離貢獻都把 v 加入隊列,就需要另行證明計數過程。
3. 為甚麼計數準確
定理
(計數 BFS 的正確性與成本)
設 與 如問題陳述一節所述。算法停止時,對每個頂點 ,dist[v] 是由 到 的最少邊數(沒有路徑則為無窮大),ways[v] 是由 到 的最短路徑數(沒有路徑則為零)。在每次精確運算成本為常數的模型下,執行時間為 ,輔助空間為 。
正確性部分在下面證明;成本界在成本一節推導。
證明
(對距離層歸納)
對距離 歸納。第零層的源點正確。假設距離為 的頂點在移出時,其計數都正確。對距離為 的頂點 ,每條最短路徑都有唯一的倒數第二個頂點 ,且 位於第 層。刪去最後一條邊得到到 的最短路徑:否則以更短的路徑替換該前綴,會得到一條到 的更短途徑;再刪去其中可能出現的環,會得到更短的簡單路徑。反過來,到這樣一個鄰居 的每條最短路徑,接上 ,都是到 的最短路徑。
不同前驅產生的路徑集合互不相交,因為它們的倒數第二個頂點不同;圖中也沒有平行邊。更新恰好對第 層的每條入邊累加對應集合一次。先進先出順序確保 移出前總和已經完整。歸納可證所有可達頂點的計數均正確。距離則由 BFS 首次發現的標準論證給出。
證明透視
為何隊列能確定最終路徑數
只有由距離 到距離 的邊能結束一條到第 層的最短路徑。即使原圖有環,這些邊構成的分層圖也是有向無環圖。先進先出次序在移出任何第 層頂點之前,先移出第 層的所有頂點,因此路徑數用於延伸路徑之前,所有有效前驅的貢獻都已到達。
4. 例題詳解
例題
(兩條路線在一個頂點會合)
取邊 、、、、、、,按列出的順序處理鄰居。移出 時發現 ,距離均為 1,各有一條路線。移出 時發現距離為 2 的 ,各有一條路線。移出 時發現 的距離已是 2,便再加一,得到 ways[c] = 2。移出 時發現 ,其 ways[t] = 2;移出 後再加一。
| 頂點 | ||||||
|---|---|---|---|---|---|---|
| 距離 | 0 | 1 | 1 | 2 | 2 | 3 |
| 路徑數 | 1 | 1 | 1 | 2 | 1 | 3 |
到 的三條路線是 、 和 。改變鄰居次序可能改變哪條路線先被發現,但不會改變最終距離或路徑數。
概念視角代數
路徑數就是鄰接矩陣的冪
設 為鄰接矩陣,當 是邊時 。矩陣 的 項,數的是由 到 、恰有 條邊的途徑數。令 :沒有更短的途徑,而恰有 條邊的途徑就是最短路徑,所以 ,其中 是使該項非零的最小指數。在上面的圖中, 的 行在 處為 、在 處為 ,而 。隊列按層計算這些數值,過程中不必真的算出任何矩陣的冪。
例題
(必須忽略的後續邊,與不可達頂點)
取邊 、、、、、,另有一個孤立頂點 。移出 時發現距離為 1 的 和 ,各有一條路線。移出 時檢查 :它已在距離 1,但 ,所以邊 被忽略,ways[b] 保持為 1;接著發現距離為 2 的 ,ways[c] = 1。移出 時檢查 ,它的距離恰為 ,所以 ways[c] 變為 2;再檢查 ,它的距離是 0 而不是 2,所以構成圈的邊 被忽略。移出 後搜尋結束。頂點 從未被發現,dist[z] 保持無窮大,ways[z] 保持為 0。到 的兩條最短路線是 和 ;途徑 有三條邊,不計入。
例題
(路徑數經瓶頸相乘)
取邊 、、、、、、、。各層為 、、、、,距離為 0 至 4。移出 時發現 ,ways[m] = 1;移出 時再加一,ways[m] = 2。移出 時發現 和 ,兩者都繼承 ways = 2。移出 時發現 ,ways[t] = 2;移出 時再加 2,得 ways[t] = 4。結果是 :每條路線都經過 ,所以 之前的兩個獨立選擇與 之後的兩個選擇相乘。若鏈上有 個這樣的菱形,從 到末端有 條路線,可見計數增長得多快。
常見錯誤
(跳過每個已被發現的頂點)
普通 BFS 遇到進入已發現頂點的邊就忽略,因為該頂點已有父頂點。若把這條規則照搬到計數算法,第一個例題中的第二條路線就會丟失:ways[c] 會停在 1 而不是 2,因為 被跳過。計數時,進入已發現頂點的邊仍須檢查,並且僅在 dist[v] == dist[u] + 1 時才作出貢獻。
常見錯誤
(對每條進入 v 的邊都累加)
相反的錯誤是對每條進入已發現頂點 的邊 都寫 ways[v] = ways[v] + ways[u],而沒有相等測試。取邊 、、:頂點 的距離為 1,恰有一條最短路徑。移出 時檢查 ,若沒有該測試,ways[b] 會變成 2,把長度為 2 的途徑 也算進去,而它並不是最短路徑。
5. 成本與限制
每個頂點最多加入隊列、移出各一次,每個可達頂點的每個鄰接表項目掃描一次。初始化所有陣列需要 ,因此在精確算術每次操作成本為常數的模型下,時間為 ,輔助空間為 (不包括鄰接表儲存)。路徑數可能隨頂點數指數增長。實際固定位寬整數可能溢位;任意精度加法的成本取決於位數,因此單位成本界並不描述位元複雜度。若計數對 取模,輸出只是餘數:餘數為零並不證明不存在最短路徑。
本證明依賴所有邊長均為 1。邊權不等時,普通 BFS 的層數未必是最短距離層,必須使用適當的帶權最短路徑方法,並證明計數何時最終確定。特別是零權邊或零權圈會帶來額外問題,不在本章計數約定內。
反例模式
按 BFS 層數計數對帶權邊不成立
斷言:邊有正權時,同一算法同樣能計算最短路徑數,只要把 dist 理解為帶權距離。取邊 、、、,權均為 1,以及權為 3 的邊 。由 到 的帶權最短距離是 2,恰有兩條路徑達到: 和 ;直接的邊代價為 3。算法數的是邊數而不是權:移出 時發現 、、,距離都是 1,ways[t] = 1,之後的邊 與 因 被忽略。它報告距離為 1、路徑數為 1,所指的是那條直接的邊,而它根本不是帶權最短路徑。單位邊長的假設正是令邊數等於距離的條件,因此這個定理不能套用於此;必須使用帶權最短路徑方法。
6. 即時檢查
快速檢查
(在第一個例題中,若刪去邊 ,dist[t] 與 ways[t] 各是多少?)
解答 · 答案
刪去 後剩下路線 和 。 的距離仍為 3,ways[t] = ways[c] = 2。
快速檢查
(當邊 連接兩個 dist[u] == dist[v] 的頂點時,為甚麼不把 ways[u] 加到 ways[v]?)
解答 · 答案
到 的最短路徑接上 後有 dist[u] + 1 條邊,比 dist[v] 多一條。它是到 的途徑,但不是最短路徑,所以不能計入。
快速檢查
(對邊 、、、、、、、,求 dist[t] 與 ways[t]。)
解答 · 答案
各層為 、、、,所以 dist[t] = 3。 與 都可由 和 到達,所以 ways[c] = ways[d] = 2,ways[t] = 2 + 2 = 4。換個說法,一條最短路徑要在 中選一個、在 中選一個: 條。
快速檢查
(算法中的所有計數都對 1000 取模,而 ways[t] 報告為 0。能否斷定 不可達?)
解答 · 答案
不能。恰好 1000(或 2000 等)條路徑同樣會得到餘數 0。是否可達要看 dist[t] 是否有限,而不是看餘數。