dijkstra的最短路徑算法回溯？

Question

我正在嘗試使用map reduce來實現dijkstra的最短路徑算法。

我有兩個問題：

1. 這是否算法回溯到重新評估的情況下，距離的距離原來是少了不選擇的路徑。例如 - > 1-> 2-> 5和2-> 3-> 2將這些值視爲權重，並且可能有2條到目的地路徑1的路徑被選爲1，但路徑的總權重小於路徑2即2-> 3-> 2，所以想知道dijkstra的算法是否需要關注回溯。

2. 請給我一個關於map和reduce函數在這種情況下的簡要概念。我正在考慮在map函數中發射reduce函數，並在reduce函數中迭代相關的權重以找到最小加權的鄰居..但在此之後它如何工作。請給我一個關於它是如何在羣集中從頭開始以及內部會發生什麼的好主意。

Answer 1

Dijkstra's不執行回溯以重新評估距離。

http://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif

是GIF應該幫助您瞭解如何Dijkstra算法重新評估距離。它通過在節點n中存儲「到節點n的最短路徑」來避免回溯的任務。

在遍歷期間，如果算法再次遇到節點n，它將簡單地比較它到達節點n的當前「距離」並將其與存儲在節點n中的數據進行比較。如果它更大，則忽略它，如果它更小，它會替換節點n中的數據。

但是，在處理消極的邊緣時，Dijkstra's會受到限制，因爲在某些情況下最終會產生負面循環，所以這是您應該警惕的。