圖均有限且有向。除非題目明確改變假設,邊權均非負。使用教學正文中的嚴格改進前驅規則。
溫習路線。 源點從零開始,鬆弛出邊,確定目前標號最小的頂點,並由前驅重建路線。使用證明之前檢查每條邊的權重符號。
檢查清單。 暫定表示已發現,並非最終確定。忽略舊堆快照。這些追蹤中相等鍵值按字母順序處理。最短路徑最小化的是總權重,不是邊數。
1. 更便宜的路線稍後到達
例題
(更便宜的路線稍後到達時的確定次序)
邊為 (6)、(1)、(2)、(5)、(2)、(7)、(1)。給出確定順序、最終距離和到 的一條最短路徑,並解釋為甚麼在首次發現時固定 是錯誤的。
解答。 處理 後標號為 。確定 ,將 改進為 並發現 。確定 ,將 改進為 並發現 。確定 並將 改進為 ;然後確定 。舊快照被跳過。確定順序為 ,對應距離為 。前驅給出 ,成本 。首次發現時就固定會把 凍結為 6,儘管稍後存在成本 3 的路線。
例題
(零權邊與平局)
邊為 (0)、(0)、(0)、(2)和 (2)。給出確定順序、距離和 pred[t]。掃描 後,標號為 (pred[a]=s)和 (pred[t]=s)。確定 :發現 ,pred[b]=a;而 給出 ,與目前標號相等,不是嚴格改進,所以 pred[t] 仍為 。確定 :邊 指向已確定的頂點,被跳過,因此零權圈 不會造成前驅迴圈。確定 。確定順序為 ,距離為 。pred[t] 記錄的路線 是最短的; 與它並列。
例題
(無法到達的目標)
邊為 (4)、(1)和 (1);頂點 與 不能從 到達。確定 ,發現 ,pred[a]=s。確定 :邊 指向已確定的源點,被跳過。此時堆已空,執行結束,、、。由於 dist[t] 為無窮大,答案是沒有到 的路線;pred[t] 仍是 none,不沿前驅鏈追蹤。
常見錯誤
(選擇邊數最少的路線)
最短路徑最小化的是總權重,不是邊數。在第一個例題中,路線 有兩條邊,成本為 ;最短路徑 有四條邊,成本只有 。廣度優先搜尋會給出前者。
常見錯誤
(把暫定標號當作距離)
在第一個例題中,掃描 後 的標號是 6,但它的距離是 3。暫定標號只是已發現路線的成本,在頂點被確定之前,它只是距離的上界。
2. 負邊破壞證明
反例模式
負邊使最小值確定規則失效
斷言:對任何有限邊權,確定目前暫定標號最小的頂點都是安全的。考慮 (2)、(5)、()。掃描 後,標號為 ,所以規則先以 2 確定 。稍後 給出成本 的路線 。這是到 的真實距離,因為該圖只有這兩條到 的路線。已確定的值 2 錯誤。證明中,到 的前綴成本為 5,大於完整最短路線成本 1;有負的最後一條邊時,前綴成本不一定不超過全程成本。修正辦法就是那個假設本身:負邊不在 Dijkstra 的保證範圍內,邊權必須非負。
3. 即時檢查
快速檢查
(對邊 (3)、(1)、(1)和 (1),給出確定順序、到 的距離和一條最短路線。)
解答 · 答案
處理 後,標號為 、。確定 ,把 改進為 。確定 ,發現 。然後確定 。確定順序為 ,到 的距離為 3,路線為 ,成本 ;路線 的成本是 4。
快速檢查
(在第一個例題中, 以距離 3 確定之後,數對 仍留在堆中。它被取出時會怎樣?)
解答 · 答案
它在 之後才被取出,因為它的鍵值 6 較大。此時 已確定,所以這個數對被跳過,不掃描任何邊。舊數對 的情況相同。
快速檢查
(在第一個例題中,哪條到 的路線邊數最少?它的成本是多少?)
解答 · 答案
路線 有兩條邊,成本為 。最短路徑成本為 6,用了四條邊,所以邊數最少的路線並非最便宜。
來源:Dijkstra 算法。