兩題都使用有限有向圖和非負權重,應用教學正文中的快照堆與嚴格改進規則。
溫習路線。 透過確定過程追蹤暫定距離和平局規則。區分目標確定時已知甚麼,以及完整執行後已知甚麼。重建路徑時,檢查相等距離的更新如何影響前驅。
檢查清單。 容許零權。過期快照不是一次新的確定。嚴格更早的確定時間為前驅連結定向。目標處提前停止只保證目標,不保證其他所有距離。
1. 相等標號與提前停止
例題
(相等標號與提前停止)
邊為 (2)、(2)、(2)、(2)、(2)、(8)、(8)和 (1)。頂點 孤立。堆鍵相等時按字母排序,按列出順序處理各頂點的出邊。給出確定順序、所有最終距離及到 的一條前驅路線。如果確定 後立即停止,且不掃描其出邊,哪個可達頂點仍未被發現?
解答。 確定 ,發現 。先確定 ;它發現 。確定 時給兩者提供相同成本,嚴格改進規則不改變它們的前驅。確定 ,將 改進為 6;確定 ,再發現並確定 。 保持無窮大。因此確定順序為 ;距離為 。一條路線為 ,成本 6;經過 的另一條路線也最短。如果確定 後不掃描其出邊就立即停止, 儘管可達仍未被發現;已確定的目標距離 6 仍然正確。
例題
(目標的首次發現與確定)
邊為 (10)、(2)和 (3)。掃描 時發現 ,標號為 10,pred[t]=s;同時發現 ,標號為 2。若在首次發現 時停止,會報告成本 10 的路線 。改為確定 :邊 給出 ,是嚴格改進,所以 、pred[t]=a。現在確定 並停止:目標以距離 5 得到保證,路線為 。舊數對 不再起作用,因為數對 會先被取出。
例題
(不同的平局規則改變路線,但不改變距離)
使用第一個例題的圖,但堆鍵相等時改為 先於 。確定 :。先確定 :發現 (pred[c]=b)和 (pred[t]=b)。確定 :它的邊給出 和 ,都與目前標號相等,所以沒有變化。確定 : 改進為 6,pred[t]=c。確定 ,然後 。距離與之前完全相同,但記錄的路線是 ,而不是 。兩者成本都是 6;平局規則決定儲存哪一條最短路線。
概念視角結構
最短路線就是緊邊構成的路徑
當最終距離滿足 時,稱權為 的邊 為緊邊。每條最短路線都只用緊邊,因為它的每個前段本身也是最短的;而由 到 只用緊邊的路線,費用必為 ,因為各項逐項相消。所以到 的最短簡單路線,恰是緊邊子圖中由 到 的簡單路徑。在第一個例題中,緊邊是 、、、、 和 ,由此得出上面找到的兩條到 的路線; 不是緊邊。前驅規則在每個可達頂點上選出一條進入它的緊邊,選哪一條則由平局規則決定。
常見錯誤
(把目標的首次標號當作最終值)
第一次得到有限標號時,該標號是一條已發現路線的成本,不一定最便宜。在含有成本 10 的邊 的例題中, 的首個標號是 10,而它的距離是 5。只應在 的目前項目被取出並確定時才停止。
常見錯誤
(以為提前停止能保證其他頂點)
在 被確定時停止,只能保證 和更早確定的頂點,而不是所有頂點。在第一個例題中,剛確定 就停止, 仍未被發現,而 根本不可達。要得到完整的距離表,必須執行到底。
2. 零權平局與前驅圈
反例模式
在平局時更新前驅可能造成圈
斷言:從已確定的 鬆弛到已確定的 ,即使只是與目前距離相等,更新 pred[v]=u 也無害。設邊為 (1)、(0)、(0)、(1)。確定 ,然後確定 ,此時 pred[a]=s。掃描 發現 ,令 pred[b]=a。確定 時, 給出相等成本 1。該變體賦值 pred[a]=b,於是 pred[a]=b、pred[b]=a;沿前驅會永遠交替。距離值卻是 。教學算法跳過指向已確定 的邊, 則設定 pred[t]=b;路線是 ,成本 2。
修正辦法是嚴格改進規則。該算法只在掃描已確定頂點指向未確定頂點的邊、且嚴格改進時設定前驅。因此前驅的確定時間早於子頂點最終被確定的時間。沿前驅連結追蹤時,確定時間嚴格遞減,所以不可能成圈。等成本路線可以存在,但這一規則只記錄其中一條。
3. 即時檢查
快速檢查
(對邊 (1)、(1)和 (2),在嚴格改進規則下 pred[t] 是甚麼?)
解答 · 答案
掃描 時 得到標號 2,pred[t]=s。之後邊 給出 ,與標號相等,不是嚴格改進,所以 pred[t] 仍是 。記錄的路線是 ; 與它並列。
快速檢查
(在第一個例題中,若剛確定 就停止,哪些頂點的最終距離已得到保證?)
解答 · 答案
已確定的頂點 的最終距離分別為 。 尚未被發現, 不可達,所以這次部分執行對兩者都沒有保證的值。
快速檢查
(對邊 (1)、(0)、(0)、(1),每個頂點各被確定幾次?)
解答 · 答案
各恰好一次。邊 指向已確定的頂點 ,被跳過;任何過期的堆數對在取出時都會被丟棄,所以零權圈 不會造成重複確定。
來源:Dijkstra 算法。