我使用 Dijkstra 演算法找到從頂點 A 到頂點 D 的最短路徑。但是邊 AB 和 AC 具有相同的權重。如果圖具有相同的權重邊，Dijkstra 演算法如何作業？
uj5u.com熱心網友回復：
Dijkstra 的演算法并沒有拋棄可能性——它使邊 AB 和邊 AC 都“處于運行中”。它通過將 B 和 C 都放在優先級佇列中來做到這一點，以它們與節點 A 的距離為鍵，在這兩種情況下都是 1。所以優先級佇列會給它們相同的優先級。根據實作——可能還有您在優先級佇列中插入這兩個節點的順序——B 或C 將是該佇列中的第一項。但最終，最終結果并不重要。
例如，如果 B 是第一個，那么在演算法的下一個回圈中，B 將從佇列中拉出，D 被推到它的距離為 6。在下一次迭代中，C 從佇列中拉出，D再次添加到佇列中（或更新——取決于實作），這次距離為 4。我們確信當我們從佇列中拉出D 時，它將是距離為 4 的版本，因此它會正確找到最短路徑。
如果 B 不是第一個，但 C 是第一個，則 D 被推入距離為 4 的佇列，當 B 被處理時，D 現在要么被拒絕（因為它的距離大于我們擁有的最小距離），要么在某些實作中，它仍然會被推送到佇列中，但永遠不會到達佇列的前面，因為 D 的另一個版本（已經在佇列中）具有更高的優先級。因此，在這種情況下，佇列也會給我們一個距離最短的 D，下次我們從中拉出 D 時。
uj5u.com熱心網友回復：
Dijkstra 的演算法計算從 A 到 D 的總成本，對邊的權重求和，最佳路線是省力的路線。聽起來很簡單。
如果有超過 1 條具有相同權重的路由，則取決于具體實作...
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/490966.html
上一篇：計算集差的最有效演算法？