每條邊的成本都是 1 時,BFS 按邊數遞增探索頂點。如果邊的成本可以是 0 或 1,最短路徑指的是權重和最小,而不是邊數最少。經過零成本邊的繞路可能勝過成本為 1 的直接邊。Dijkstra 算法能處理這些權重,但兩種取值的特殊結構容許使用更簡單的佇列:零成本改進放在佇列前端,一成本改進放在後端。
設定與溫習路線
定義 16.2.1
(0–1 最短距離)
設 是有限有向圖,源點為 ,邊權 。容許平行邊和自環:每條邊都是獨立的鄰接表項目。對無向圖,把兩個方向的關聯邊都放入表中,權重相同。路徑成本為邊權之和; 表示由 到 的最小成本,不可達時為 。零邊路徑給出 。刪去非負權圈不會增加成本,所以每個可達頂點的最小值都由一條簡單路徑達到。
先追蹤雙端佇列,觀察暫定標號如何改進;再證明兩個連續鍵值的不變量,並用它說明為甚麼可以確定頂點;最後計算邊掃描與佇列項目。佇列中儲存的鍵值是快照:頂點目前距離改進時,舊鍵值不會悄悄更新。
明確保留過期項目的算法
使用由 (key, vertex) 配對構成的雙端佇列和布林陣列 settled。假設兩端操作為常數時間,整數加法與比較精確。
對每個 v:dist[v] = infinity;settled[v] = false
dist[s] = 0
D = [(0,s)] # 左端是前端
當 D 非空:
(k,u) = pop_front(D)
如果 settled[u] 或 k != dist[u]:繼續下一次迴圈
settled[u] = true
按鄰接表順序遍歷每條邊 (u,v,w):
如果 not settled[v] 且 k + w < dist[v]:
dist[v] = k + w
如果 w == 0:push_front(D, (dist[v],v))
否則: push_back(D, (dist[v],v))
返回 dist
每個有限標號都是一條實際已發現途徑的成本。嚴格改進會建立一個新快照;舊快照仍留在佇列中,移出時被丟棄。相等候選值不產生新項目。只有目前快照被移出時才確定頂點,而非首次發現時。
概念視角組合
對零權邊封閉的距離層
設 。則 是從 沿零權邊可達的頂點集; 則是不屬於較早各層、並可由 伸出的權重 1 的邊之終點,沿零權邊到達的頂點集。在通向 的最短路徑上,最後一條權重 1 的邊之前的部分本身也是最短的,成本為 。這個算法就是對這些層作的廣度優先搜尋。
定義 16.2.2
(快照、過期項目與已確定頂點)
雙端佇列中的項目 是一個快照:記錄該項目插入時 的值。若 已確定,或 ,該項目是過期的。當 的一個非過期項目從前端被移除時, 就已確定,其標號此後不再改變。
為甚麼雙端佇列有序
引理 16.2.3
(雙端佇列的雙鍵不變量)
在每次移除步驟開始時,雙端佇列中儲存的鍵值(無論過期與否)從前端到後端非遞減,並且存在整數 ,使每個鍵值都是 或 。
證明
(對移除步驟作歸納)
每次移除開始時,所存鍵值按非遞減順序排列,且跨度最多為一:對某個整數 ,每個儲存鍵值都是 或 。起初唯一鍵值為零。移除前端,包括移除過期項目,都保持剩餘項目的這一性質。如果處理一個鍵值為 的有效項目,每次成功的零權邊鬆弛都在前端插入鍵值 ,每次成功的一權邊鬆弛都在後端插入鍵值 。因此順序和跨度保持不變。這裏討論的是所有儲存鍵值,不論過期與否;過期檢查決定是否掃描邊,而不決定項目在佇列中的位置。
為甚麼確定操作安全
定理 16.2.4
(已確定的標號是精確的)
若所有權重都在 中,則每個頂點 在被確定的一刻都有 。算法終止時,對每個頂點 都有 ,不可達者為 。
證明
(最短路徑上第一個未確定的頂點)
歸納證明每個已確定頂點都有真實最短距離。首先確定的是 ,距離為零。假設下一次有效移除以鍵值 確定 ,而此前確定的頂點均正確。其標號是一條途徑的成本,因此 。如果 ,取一條到 的最短路徑,令 為其上第一個尚未確定的頂點,其前驅 已確定。到 的前綴成本為 ;否則替換成更便宜的前綴會給出到 的更便宜途徑。處理 時,其到 的邊要麼設定、要麼保持一個不超過該路徑到 的前綴成本的標號。有限標號本身是一條途徑的成本,所以不能低於 ;因此 的目前標號為 。
分兩種情況。若 ,則 ,與有效項目檢查 矛盾。若 ,它最近一次嚴格改進留下了一個目前快照,仍在雙端佇列中:目前快照若早已被移除,就會確定 ;而剛移除的項目屬於 。這個快照的鍵值小於 ,與移除 時佇列有序矛盾。因此 。歸納也說明跳過指向已確定頂點的鬆弛是合理的。每個可達頂點最終都會被確定:否則,從已確定區域沿路徑指向某個未確定可達頂點的邊會插入一個有限有效項目,與算法終止矛盾。不可達頂點仍為無窮大,因為有限標號只由實際途徑產生。
證明透視
證明中哪兩個事實相互抵觸
證明把被移除的項目 與通往 的最短路徑上第一個未確定的頂點 比較。對前驅 的歸納給出 ,而路徑其餘部分的成本至少為 ,故 。上一個引理說明,沒有任何儲存的鍵值可以排在被移除的前端項目的鍵值 之前,因此不可能存在鍵值更小的 的當前快照。情況 是同一個矛盾,只是改與有效項目檢查 抵觸。權重屬於 的假設只在不變量內部使用:權重 的邊可能把較小的鍵值排到較大的鍵值之後,這正是下面反例所示的失敗。
例題追蹤:快照變為過期
例題 16.2.5
(一個項目變為過期)
按所示鄰接順序取邊 (權重 1)、(權重 0);(權重 0)、(權重 1);(權重 1)、(權重 0);(權重 0)。數對為 (key,vertex),左端為前端。
| 移除 | 操作 | 操作後的雙端佇列 |
|---|---|---|
| 確定;發現 | ||
| 確定;將 改進為 0,發現 | ||
| 確定;發現 | ||
| 確定;將 改進為 0 | ||
| 確定 | ||
| 跳過:過期或已確定 | ||
| 跳過:過期或已確定 |
五個距離均為零:例如 的成本為零。舊項目 和 並不是錯誤,而是已經失效的快照。相反,若直接邊首次發現 時就永久標記它,便會阻止經過 的改進。
例題 16.2.6
(自環與不可達頂點)
取頂點 與邊(依此次序)(權重 )、(權重 ); 沒有入邊。移除 並確定 。自環因 已確定而被跳過,通往 的邊給出 ,項目 放到後端。移除 即確定 ,雙端佇列變空。對 輸出 :自環不改變任何東西, 保持 ,因為只有真實的途徑才會產生有限標號。
例題 16.2.7
(全是零權重邊的圈)
取邊 (0)、(0)、(0)、(1)。移除 : 放到前端。移除 : 放到前端。移除 :回到 的邊因 已確定而被跳過, 放到後端。移除 即確定 。 的距離為 。零權重圈不需要特別處理:已確定的頂點不會再被鬆弛,所以它不會令迴圈無限執行。
複雜度與約定
命題 16.2.8
(0–1 BFS 的開銷)
設 ,並以 計有向鄰接表項目的數目。算法至多向雙端佇列插入 個項目,時間為 ,輔助空間為 。
證明
(計算掃描次數與插入次數)
記 、,每個有向鄰接表項目各計一次。初始化耗時 。每個頂點只確定一次,所以每個出邊項目最多掃描一次。每次成功的嚴格鬆弛對應一次邊掃描並插入一個數對;這種插入最多 次,加上初始數對一次。雙端佇列操作,包括移除過期項目,共 次。在所述常數時間算術與雙端佇列模型下,時間為 ,包括無邊的圖。陣列使用 空間,雙端佇列可包含 個快照,因此這一明確實作的輔助空間為 ,不計圖的表示。
對權重 2 或負權,證明不能原封不動地使用:兩個鍵值的不變量或確定標號的證明可能失效。零權圈對最小距離無害,卻可能產生無限多條等成本途徑。本算法計算距離,不計算最短途徑的數量。
反例模式
權重 2 的邊會破壞佇列次序
聲稱:同一個算法把所有正權重的邊都放到後端,對權重屬於 的圖也適用。取邊(依此鄰接次序)(2)、(1)、(0)。移除 得 、,雙端佇列為 ,次序是亂的。移除 即以標號 確定 ;之後移除 ,邊 因 已確定而被忽略。輸出 是錯的: 的成本為 。補救辦法是把權重限制在 ,或對一般的非負權重改用以堆實作的 Dijkstra 算法。
常見錯誤
常見錯誤
(邊數最少不等於成本最低)
權重為 的直接邊只用一條邊,而兩條零權重邊的繞路成本為 。依邊數排序的普通 BFS 會報告直接邊;在上面的追蹤中,它會給出 而不是 。
常見錯誤
(頂點一被發現就標記為已訪問)
由權重 的邊得到的標號,仍可能被稍後處理的零權重繞路改進。若邊 一發現 就把它標記為已確定,便會擋住經由 的改進。只有在非過期項目從前端被移除時才確定頂點。
檢查清單
- 寫明有向或無向鄰接約定、 及權重屬於 。
- 權重 0 放前端,權重 1 放後端;保留鍵值快照。
- 跳過過期或已確定的項目;在移除時而非首次發現時確定頂點。
- 分別證明佇列有序和最短距離正確,並區分兩者。
- 統計邊掃描與排隊快照;計入初始化與無邊圖。
練習
快速檢查
(依下列鄰接次序對邊 (1)、(1)、(0)、(0)執行算法。寫出每次移除後的雙端佇列與最終距離。)
序對為(鍵值,頂點),左端為前端。
解答 · 答案
移除 :、 放到後端,得 。移除 :確定 ;權重 0 的邊給出 放到前端,得 。移除 :確定 ,得 。移除 :確定 ;通往 的邊被跳過,得 。 的距離為 。
快速檢查
(邊依次為 (1)、(0)、(0)。若把權重 0 的改進放到後端而不是前端,算法對 輸出甚麼? 又是多少?)
寫出移除 之後的雙端佇列。
解答 · 答案
移除 得 放到後端,接著 也放到後端:。次序顛倒的項目 先被移除,以標號 確定 ;之後的邊 被忽略。輸出為 ,但經 可得 。把零成本的改進放到前端,才能保證較小的鍵值排在前面。
快速檢查
(圖是無向圖,有 條邊,每條權重為 或 。界 中的 是多少?)
回想無向邊是怎樣儲存的。
解答 · 答案
每條無向邊貢獻兩個有向鄰接表項目,所以 。因此界 即 ,但雙端佇列的插入次數可以達到 。