成本為 7 的直達道路可能不如成本分別為 2 和 1 的兩段道路。BFS 計算邊數,因此一般不能選出加權圖中最便宜的路線。Dijkstra 算法記錄目前發現的最便宜路線成本,並總是確定目前暫定成本最小的頂點。
本課在現有的 Dijkstra 單元上補充快照堆實作、詳細追蹤和附解答的短練習。
1. 約定與實作
設 為有限有向圖,源點 ,所有邊權均為非負實數。容許零權邊。無向邊可表示為兩個有向鄰接項目,平行邊分別計作獨立項目。目標是求從 到每個頂點的最小邊權和;不可達頂點的距離為 。
定義
(暫定標號、鬆弛與已確定頂點)
有限的暫定 dist[v] 是一條已發現途徑的成本,因此是真實最短距離的上界。沿邊 的一次成功鬆弛,在 dist[u] + weight(u,v) 嚴格較小時替換 dist[v],並在嚴格改進時記錄 pred[v]=u。頂點以目前鍵值從堆中被取出時即已確定,此後它的標號不再改變。
以下實作使用不可變 (distance, vertex) 快照構成的最小堆。相同鍵值按字母順序打破平局,只為使追蹤可重現;正確性不依賴此規則。
對 v in V:dist[v] = infinity;pred[v] = none;settled[v] = false
dist[s] = 0;heap = [(0,s)]
當 heap 非空:
(k,u) = extract_min(heap)
如果 settled[u] 或 k != dist[u]:繼續下一次迴圈
settled[u] = true
對每條從 u 出發的邊 (u,v,w):
如果 not settled[v] 且 k+w < dist[v]:
dist[v] = k+w;pred[v] = u
insert(heap, (dist[v],v))
返回 dist, pred
後續改進不會改變堆中的舊快照。舊數對被取出時,過期或已確定檢查會阻止再次掃描出邊。按本規則,相等的候選距離不會替換前驅。每個有限標號都來自實際發現的途徑;無窮大是數學哨兵,實作時須安全處理,避免不安全算術。
2. 為甚麼最小目前標號可以安全確定
定理
(Dijkstra 算法的正確性)
設所有邊權均為非負。當頂點 以鍵值 被確定時,,即從 到 的真實距離。因此算法停止時,對每個可達頂點 ,dist[v] 等於 ;對每個不可達頂點,dist[v] 為無窮大。
證明
(按確定次序歸納)
假設此前所有已確定標號都是真實最短距離。設下一次確定的頂點為 ,目前鍵值為 。已發現路線給出 。假設 。取一條到 的最短路徑,令 為其上第一個尚未確定的頂點,其前驅 已確定。非負權確保該路徑到 的前綴成本不超過 ;該前綴本身也是到 的最短路徑。確定 時,鬆弛使 dist[x] 至多等於該前綴成本,而有限暫定標號不能低於真實最短距離。因此 dist[x] = delta(x) <= delta(u) < k。
若 ,這與目前項目檢查 k == dist[u] 矛盾。否則 有一個目前堆快照:目前快照若此前已被取出,就會確定 。它較小的鍵值應先於 被取出,與最小堆規則矛盾。故 。源點從零開始,歸納完成證明。比較前綴與完整路線時用到了非負權;這個貪心論證不能不加修改地用於負邊。
證明透視
確定證明中每個假設在哪一步使用
證明是在第一次錯誤確定處導出矛盾,每個假設都在可指認的一步中使用。歸納假設(此前每個已確定的標號都精確)使 的已確定前驅 精確,所以鬆弛 後,dist[x] 至多等於前綴成本。非負權只用在一個不等式 :到 的最短路徑的前綴不可能比整條路徑更貴。若最後一條邊為負,這一環節失效,定理也隨之失效。有限標號不會低於真實距離,這使 dist[x] 由上界變為精確值 。堆次序最後才用到: 的目前快照鍵值小於 ,所以會先於 被取出,與 的選取矛盾。 的情形由檢查 k == dist[u] 排除。論證之所以收尾,是因為 不可能,所以每次確定都精確;歸納會結束,因為每個頂點至多被確定一次。
命題
(前驅鏈)
算法停止後,對每個可達的非源點頂點 ,頂點 pred[v] 在 之前被確定;從 沿前驅指標追蹤,會在有限步內到達 ,反轉該序列就是由 到 的一條最短路徑。有零權邊時同樣成立。
證明
(前驅在確定時間上指向過去)
嚴格改進時記錄的前驅,總是從尚未確定的頂點指向設定該指標時已確定的頂點。沿最終前驅指標反向追蹤,會在確定時間上不斷倒退,因此即使有零權邊也不可能成圈。此外,pred[v]=u 最後一次設定時,dist[v]=dist[u]+weight(u,v) 成立,而 dist[u] 當時已是最終值,所以沿鏈各邊權相加得 dist[v],由定理它等於 。對可達的非源點目標,沿前驅追蹤到 並反轉序列。若 dist[target] 為無窮大,則報告沒有路線。只保留一個前驅會給出一條最短路線,不一定給出所有並列路線。
3. 例題追蹤
例題
(含過期快照的追蹤)
取邊 (7)、(2)、(1)、(6)、(1)、(8)、(3)。堆鍵相等時按字母排序。表格記錄掃描每個已確定頂點之後目前的有限距離。
| 已確定 | |||||
|---|---|---|---|---|---|
| 0 | 7 | 2 | |||
| 0 | 3 | 2 | 8 | ||
| 0 | 3 | 2 | 4 | 11 | |
| 0 | 3 | 2 | 4 | 7 | |
| 0 | 3 | 2 | 4 | 7 |
舊數對 在 之前被移除並跳過,因為 已確定;舊的 和 稍後也被跳過。 的前驅鏈為 。反轉得到 ,成本為 。
概念視角幾何
已確定頂點構成不斷擴大的球
想像一團火從 出發,越過每條邊所需的時間等於邊權,於是 在時刻 着火。被取出的鍵不會減小,而且對每個半徑 ,鍵不超過 的已確定頂點,恰好構成球 。在追蹤例子中,半徑 的球含 (),半徑 時再加入 。暫定標號是球外緊鄰頂點的預測着火時刻,沿離開球的邊得出。非負邊權使時間向前流動:負邊會令頂點比它的來源更早着火。
例題
(零權邊與過期快照)
取邊 (0)、(0)、(5)和 (0)。確定 :發現 (pred[a]=s)和 (pred[b]=s)。確定 :邊 給出 ,是嚴格改進,所以 、pred[b]=a,並插入新數對 。確定 :發現 ,pred[t]=b。確定 。舊數對 最後被取出並跳過,因為 已確定。所有距離都是 0,前驅鏈 就是成本為 0 的路線 。
例題
(不可達頂點與指向源點的邊)
取邊 (4)、(1)和 (2);頂點 不能從 到達。確定 ,發現 ,pred[a]=s。確定 :邊 指向已確定的源點,被跳過,因為已確定的頂點不再被鬆弛。堆已空,執行結束,、、,pred[c]=none。邊 從未被掃描,因為 從未被確定。
常見錯誤
(把暫定標號當作距離)
在追蹤中掃描 之後,dist[a]=7,但從 到 的距離是 3。暫定標號是已找到路線的成本,在頂點被確定之前只是上界。
常見錯誤
(掃描過期數對的出邊)
若省去檢查 settled[u] or k != dist[u],舊數對 會第二次掃描 的出邊。標號不會因此改進,因為它的鍵值不小於精確標號,所以輸出不變;但成本會變:一個頂點可能被掃描多次,每個快照一次,「每個鄰接項目只掃描一次」的界便失效,下面的時間界也隨之失效。
4. 成本與停止條件
命題
(快照堆的執行時間)
使用鄰接表、精確的常數時間算術及二叉最小堆時,算法的執行時間為 ,不計圖本身的儲存,輔助空間為 。
證明
(計算掃描、插入與堆操作的次數)
假設使用鄰接表、精確的常數時間算術及二叉最小堆。初始化陣列耗時 。每個頂點只確定一次,每個出邊鄰接項目最多掃描一次。成功鬆弛最多 次,因此插入的快照最多 個。堆操作耗時 。總時間為 ,包括不連通和無邊情況。不計圖儲存,陣列與堆使用 輔助空間。
具有 decrease-key 的索引堆有不同的空間與操作次數,不能悄悄把一種實作的界套到另一種上。
如果只需要一個目標的距離,在其目前項目被取出並確定時停止是正確的。首次發現時停止則不正確:更便宜的路線可能稍後到達。提前停止不能計算其他所有距離;若在掃描目標的出邊之前停止,仍可達的頂點可能尚未被發現。
反例模式
目標的首個有限標號不是它的距離
斷言:目標 一得到有限標號,搜尋就可以停止。在上面的追蹤中, 在 被確定時首次得到標號:邊 給出 ,pred[t]=a。此時停止會報告路線 ,成本 。但稍後確定 會把 改進為 ,真實距離是 7,路線為 。修正辦法是只在 的目前數對被取出並確定時才停止;在這個追蹤中就是數對 。
5. 即時檢查
快速檢查
(對邊 (4)、(1)、(2)和 (1)執行算法。給出到 的距離及其前驅鏈。)
解答 · 答案
處理 後,標號為 、。確定 ,把 改進為 3。確定 ,發現 。然後確定 。到 的距離為 4,前驅鏈為 ,路線 的成本為 。
快速檢查
(在例題追蹤中,一共插入多少個快照?其中有多少個在取出時已過期?)
解答 · 答案
先插入源點數對 ,而 7 條邊每條都產生一次成功鬆弛,所以共插入 個快照。其中五個用於確定 。另外三個 、 和 已過期,被跳過。
快速檢查
(在例題追蹤中,pred[a] 被賦值幾次?為甚麼之後不再改變?)
解答 · 答案
兩次:掃描 時 pred[a]=s(標號 7),掃描 時 pred[a]=b(標號 3,嚴格改進)。 被確定之後,沒有任何鬆弛再以它為目標,所以它的前驅已是最終的。