到達某個頂點的暫定路線,只是最短路徑距離的一個上界,並不自動成為最終答案。Dijkstra 算法指出何時可以安全地確定其中一個上界:在尚未確定的頂點中,選目前暫定距離最小的一個。非負邊權保證,之後經過未確定區域的路線,不可能改善這個選擇。
數學上的選擇與優先隊列的實作有關,卻不是同一件事。一個頂點可以在堆中有多項記錄,因為舊路線可能被較短的新路線取代。我們先證明貪心步驟,再說明哪些記錄仍然有效、何時可以提早停止,以及存在平行邊或零權環時,前驅邊為甚麼仍能給出有意義的路徑。
定義圖與暫定距離的含義
定義 7.2.1
(非負有向最短路徑)
設圖 的頂點為 ,其中 ,源點為 。邊權為非負整數,容許平行有向邊與自環。每條邊以它在固定輸入邊列表中的位置作識別碼。
以 表示從源點到 的最小路徑權重;不存在路徑時為 。源點的距離是零,由空路徑作見證。由於所有權重非負,從遊走刪去一個環不會增加權重,所以每個可達頂點都有一條最短簡單路徑。
初始化 ,其餘暫定標號均為 。處理有限標號頂點 時,對權重 的出邊作鬆弛:檢查是否有 。若有,就用該候選取代 ,並記錄哪條邊帶來這次改善。
引理 7.2.2
(標號是上界)
在算法的任何時刻,對每個頂點 都有 。
證明
(每個有限標號都有見證遊走)
每個有限標號都是某條已發現源點遊走的權重。源點的零標號如此;鬆弛時,以 取代 ,它是取得 的遊走再接上一條邊的權重。任何遊走的權重至少為 ,所以候選可以太大,卻不會比真正最優值更小。無窮標號顯然滿足不等式。
定義 7.2.3
(已確定頂點)
當頂點的標號已證明為最終值,即 ,它便稱為已確定,其出邊只掃描一次。尚未確定的標號仍是暫定值,即使已改善多次。
證明為甚麼最小目前標號可以確定
定理 7.2.4
(最小的未確定標號就是最終值)
設所有邊權非負。每當算法確定頂點 (它被選為未確定頂點中有限標號最小者)時, 的標號在該時刻等於 。
證明
(跨越已確定區域的邊界)
歸納起點是源點:它的標號為零,而任何非負權遊走都不可能更短。假設所有較早確定的頂點都已得到真正距離。設 是尚未確定頂點中,有限暫定標號最小的一個。它可達,因為有限標號有一條源點遊走作見證。
取從 到 的最短路徑,設 是路徑上第一個尚未確定的頂點,其前一頂點 已確定。最短路徑的前綴本身也最短;否則可替換該前綴,得到更短的源點至 遊走。因此,處理 時,鬆弛到 的邊曾給出
再配合上界不變量,便有 。從 到 的剩餘路徑權重非負,所以 。因為 的未確定標號最小,
所有不等式都必須取等,故 。確定 後,歸納假設繼續成立。
證明透視
每個不等式由哪項事實收尾
不等式鏈用到四項各自獨立的事實。所選標號的最小性給出 ,因為 未確定而且標號有限。把歸納假設用於已確定的前驅 ,再加上上界引理,便得到精確值 。非負性只用一次,說明從 到 的後綴不會降低權重,即 。上界引理以 把鏈首尾相接。
不明顯的一步是討論邊界頂點 ,而不是 本身。 的標號可能經未確定頂點形成,直接看不出甚麼。 恰在已確定區域之外一步,鬆弛已經完成,而且它在通往 的最短路徑上。鏈由 出發,又回到 ,所以每個不等式都必須取等。若後綴可以有負權重,中間的不等式便不成立,下面的反例正是這種情況。
證明針對的是具有有限標號的可達頂點。若再沒有有效堆記錄,就不可能仍有可達但未確定的頂點:否則到達它的一條源點路徑,必跨越一條從已確定頂點到未確定頂點的邊;該鬆弛會提供有限標號和待處理記錄。不可達頂點從不會被確定,並保留無窮標記。
反例模式
負邊破壞非負後綴的論證
取邊 ,權重一;,權重四;以及 ,權重 。貪心算法會在處理 前,把 的距離確定為一;但到 的最短路線權重是 。
圖中根本沒有有向環。失敗原因是負邊:從路徑上的未確定頂點出發,後綴可能降低總權重,令貪心證明中間的不等式失去依據。以下實作拒絕所有負權輸入邊,包括從所選源點不可達的邊。Bellman–Ford 處理的是另一種邊權情況。
分清目前標號與堆記錄
定義 7.2.5
(堆記錄、有效與過時)
堆記錄 表示在較早某個時刻,曾發現一條長度為 的路線到達 。若 而且 尚未確定,記錄稱為有效,否則稱為過時。過時記錄未必等於目前標號 。
惰性實作在路線改善時不直接修改既有堆項,而是加入新記錄,讓舊記錄留待稍後丟棄。
從堆取出記錄時,只有鍵值仍等於目前暫定標號,而且頂點尚未確定,才可以用它確定該頂點。在掃描出邊前,跳過所有已過時或頂點已確定的記錄。
定理 7.2.6
(惰性記錄保持貪心選擇)
每當迴圈取出一項未被跳過的堆記錄 ,便有 ,而且 在未確定頂點中標號有限且最小。
證明
(每個未確定標號都有仍在堆中的記錄)
每當標號變為有限或改善,便加入 。記錄只會因被取出而離開堆,而通過兩項檢查的取出記錄會確定其頂點。因此,每個標號有限的未確定頂點,其記錄 仍在堆中。堆給出最小記錄,所以通過兩項檢查的取出記錄,對每個這樣的 都滿足 。特別是 , 達到最小值。
例題 7.2.7
(舊堆鍵值在多次改善後仍然存在)
取源點 0,頂點 ,固定邊列表如下:
| 邊識別碼 | 有向邊 | 權重 |
|---|---|---|
兩條從 0 到 1 的邊是不同記錄。頂點 3、4 構成零權環,頂點 5 則不可達。堆的平手次序按頂點識別碼決定。
| 確定的頂點 | 之後標號,按頂點次序 | 主要改善 |
|---|---|---|
| 頂點 1 先得到 8,再得到 5 | ||
| 頂點 1 改善至 3 | ||
| 頂點 3、4 改善 | ||
| 零權邊改善頂點 4 | ||
| 沒有嚴格改善 |
確定頂點 1 後,舊記錄 仍然存在,並因頂點識別碼平手次序,在 前取出。它已過時,不會重新掃描頂點 1。記錄 、、 最後也會被跳過。表格只記確定事件,並非每次從堆取出記錄的事件。
最後的前驅邊識別碼為 。到頂點 4 的路線使用邊識別碼 ,即 ,權重為 。
零權平手不需要改寫相同距離
採用嚴格改善測試。若另一條路線長度恰好等於目前值,就保持標號和前驅不變。這會找到一條最短路徑,卻不會列舉所有最短路徑,也不承諾找到字典序最小的一條。
定理 7.2.8
(前驅鏈通回源點)
執行完畢後,對每個可達的非源點 ,沿前驅邊由 走去,每一步都到達更早確定的頂點,並最終到達 ;即使有些邊權為零也是如此。
證明
(前驅先被確定)
在實作中,只有已確定頂點能發出鬆弛,而已確定的目標會被跳過。因此,尚未確定頂點得到前驅邊時,其前驅必已確定。若它在被確定前再次更換前驅,新前驅仍然比它更早確定。
執行完畢後,每個可達非源點沿前驅走一步,都會到達更早確定的頂點。因此,即使有零權邊,前驅鏈也不可能成環。又因源點是唯一沒有前驅的可達頂點,前驅鏈最終必到達源點。
存在平行邊時,要儲存前驅邊識別碼,而不只是前驅頂點識別碼。相同端點之間可以有不同權重的邊,所以頂點序列本身未必指出鬆弛真正選中的那條見證邊。
完整的惰性堆實作
輸入是固定有向三元組列表 (from_vertex, to_vertex, weight),以前提要求頂點識別碼及權重都是整數。None 代表不可達距離,與合法零距離分開。搜尋前會檢查每條邊的端點範圍及權重非負性,但不在執行時檢查整數型別。Python 整數令例題的和保持精確。
from heapq import heappop, heappush
def dijkstra(n, edges, source):
if n < 1 or not 0 <= source < n:
raise ValueError("a positive vertex count and valid source are required")
edges = tuple(edges)
adjacency = [[] for _ in range(n)]
for edge_id, (u, v, weight) in enumerate(edges):
if not 0 <= u < n or not 0 <= v < n or weight < 0:
raise ValueError("edge endpoints must be valid and weights nonnegative")
adjacency[u].append((v, weight, edge_id))
distance = [None] * n
predecessor = [None] * n
settled = [False] * n
distance[source] = 0
heap = [(0, source)]
while heap:
candidate, u = heappop(heap)
if settled[u] or candidate != distance[u]:
continue
settled[u] = True
for v, weight, edge_id in adjacency[u]:
if settled[v]:
continue
proposal = candidate + weight
if distance[v] is None or proposal < distance[v]:
distance[v] = proposal
predecessor[v] = edge_id
heappush(heap, (proposal, v))
return distance, predecessor
def restore_path(edges, predecessor, source, target):
if target == source:
return []
if predecessor[target] is None:
return None
path = []
while target != source:
edge_id = predecessor[target]
path.append(edge_id)
target = edges[edge_id][0]
return path[::-1]
調用 restore_path 時,要使用未經改動且可按下標存取的原邊列表,以及同一源點執行所得的前驅陣列,目標也必須合法。目標是源點時返回空邊列表;不可達時返回 None;可達時按前進次序返回明確的邊識別碼。成本與路徑長度成正比,而路徑最多有 條邊。
對例題圖,dijkstra(6, edges, 0) 返回距離 [0,3,2,5,5,None] 和前驅 [None,3,1,5,7,None]。重建目標 4 得到 [1,3,5,7];目標 5 則得到 None。
例題 7.2.9
(最小的例子與零權自環)
取 ,源點 ,唯一的邊為 ,即權重為零的自環。堆由 開始。取出該記錄便確定頂點 ;掃描自環時,發現目標已確定而跳過,所以沒有加入新記錄。結果為 distance = [0] 與 predecessor = [None],對目標 ,restore_path 返回空列表。零距離是真實的值,與不可達標記 None 不同。
在確定時停止,而不是首次發現時
反例模式
第一條到達目標的路線可能長得多
取邊 ,權重九;,權重二;以及 ,權重一。處理源點時,會以標號九發現目標 。若立即停止,就返回錯誤答案;經 的路線權重為三。
若只要求目標距離,當一項目前有效記錄確定目標時停止,由貪心證明可知是正確的。但那時其他未確定標號未必已是最終值。提早停止的介面不能把整個暫定陣列當成已完成的最短路徑答案。以上函數刻意完整執行。
例題 7.2.10
(在確定時正確停止)
取邊 權重九、 權重二、 權重一,堆由 開始。確定 時加入 和 。接著取出 並確定 ;候選 改善 ,加入 。此時 是最小記錄且通過兩項檢查,所以 以距離三確定,只求目標的搜尋可以停止。記錄 仍留在堆中,已經過時,從不會被檢視。
除頂點外,也要計算堆記錄數
以 表示輸入邊記錄數。
命題 7.2.11
(惰性堆實作的成本)
此實作最多加入 項堆記錄,時間為 ,空間為 ,包括鄰接表和堆。
證明
(計算確定、鬆弛與記錄的次數)
初始化與驗證需要 工作。每個頂點最多確定一次,所以每條出邊最多掃描一次。成功鬆弛最多 次,因此連源點在內,最多加入 項記錄。每項記錄最多取出一次,每次花費 。
惰性堆可能同時有 項記錄,而不是每個頂點只有一項。多重圖可以在 很小時仍有任意多條平行邊,因此不能只由頂點數就假設每次堆操作的界限為 。
例如,只有兩個頂點,把源點至目標的平行邊按權重嚴格遞減列出。掃描源點時,每條邊都改善目標一次,而任何目標記錄都尚未取出,所以這些記錄會同時留在堆中。每個頂點只存一項、支援 decrease-key 操作的索引優先隊列,具有另一套空間與操作分析。
這個界限計算算術及比較操作;固定位元整數的加法不可默默溢出。無論選哪一種適當隊列,正確性都依賴非負權重、選取目前最小標號,以及分清暫定與已確定狀態。
常見錯誤
常見錯誤
(用真假值檢查距離)
把 distance[v] is None 寫成 not distance[v],會把合法的距離 當作不可達。取源點 和邊 、、,確定頂點 時,正確的 會被改寫成 ,頂點 於是以距離 而非 被確定。
常見錯誤
(對已確定頂點接受等長候選)
假設更新條件改為 proposal <= distance[v],而且不跳過已確定的目標。對零權邊 、、,確定 時會把 的前驅改寫成邊 。從 出發的前驅鏈便在 與 之間來回,永遠到不了 ,路徑重建不會終止。嚴格比較加上已確定檢查可排除這種情況。
練習與詳解
快速檢查
(重建精確的多重圖見證)
對例題圖,求到頂點 4 的最終距離,以及按前進次序的前驅邊鏈。存在平行邊時,為甚麼只記前驅頂點識別碼提供的資訊較少?
解答 · 答案
距離是五。邊識別碼 給出 ,權重依次為 。同一對頂點可有不同權重的多項邊記錄;邊識別碼確定實際選中的見證,而不只是它的頂點序列。
快速檢查
(選擇正確的目標停止條件)
對邊 、、,在 t 首次得到有限標號時停止有甚麼問題?只搜尋目標時,何時才可安全停止?
解答 · 答案
第一個標號是九,但經 的最短路線長度為三。跳過已過時或已確定的候選後,當目標以目前有效最小值取出並被確定時,目標搜尋才可停止。這並不一併核實其餘暫定陣列已完成。
快速檢查
(解讀過時的堆候選)
頂點 1 的標號已改善至三,堆卻仍包含 。取出該記錄時,應再掃描頂點 1 的邊嗎?若實作保留已確定檢查,舊鍵值等式測試是否獨立必要的正確性條件?
解答 · 答案
應跳過過時記錄,不再掃描。在嚴格改善與最小堆下,較小的新記錄必先於舊記錄取出。因此,已確定檢查本身已能阻止重複掃描;明確的等式測試是清楚的目前候選檢查,但不是此實作中獨立必要的條件。
快速檢查
(解釋零權環為甚麼不令返回路徑成環)
例題頂點 3、4 之間有雙向零權邊。為甚麼沿返回的前驅邊仍不可能循環?程式如何處理相等長度的候選?
解答 · 答案
每個選中的前驅都比其尚未確定的目標更早確定,所以前驅鏈沿確定次序嚴格向後走,不可能成環。程式跳過已確定目標,並只接受嚴格改善,令相等長度候選和源點的空路徑根保持不變。
快速檢查
(用正確參數限制惰性堆)
只有兩個頂點,源點至目標有 m 條按權重遞減列出的平行邊。處理源點後,可同時存在多少項目標記錄?為甚麼頂點數不能限制此堆的儲存量?
解答 · 答案
全部 項目標記錄可以同時存在,因為每條邊都在下一次堆取出之前改善標號並加入新記錄。惰性加入保留了已被取代的候選,因此儲存量依賴邊記錄數。一般堆對數界限用 ;每頂點只保留一項的 decrease-key 實作是另一種數據結構。
快速檢查
(分清零距離、不可達與禁止的邊權)
若 權重為零,而 b 不可達,函數對 s、a、b 應返回甚麼距離標記?不可達分量內的負邊是否符合本節輸入條件?
解答 · 答案
依次為零、零及 None。零權路線是真實有限最短路徑,不是無窮標記。即使負邊不可達,函數仍會拒絕,因為輸入條件要求每條邊都非負,而且驗證在遍歷前完成。