什麼是你知道的最快的Dijkstra實現（用C++）？

我最近將Dijkstra算法的第三版本添加到我的項目中，以獲得最短路徑的單一源代碼。什麼是你知道的最快的Dijkstra實現（用C++）？

我意識到有很多不同的實現在性能上有很大的不同，而且在大圖中結果的質量也會有所不同。使用我的數據集（> 100.000個頂點），運行時間從20分鐘到幾秒不等。最短路徑也相差1-2％。

哪一個是你認識的最好的實現？

編輯： 我的數據是一個液壓網絡，每個節點有1到5個頂點。它可媲美街道地圖。我對已經加速的算法進行了一些修改（對所有剩餘的節點使用排序列表），現在可以在一小部分時間內找到相同的結果。我已經搜索了這樣的事情很長一段時間。我想知道這樣的實現是否已經存在。

我無法解釋結果中的細微差異。我知道Dijkstra不是啓發式的，但所有的實現似乎都是正確的。較快的解決方案具有較短路徑的結果。我專門使用雙精度數學。

編輯2： 我發現找到的路徑的差異確實是我的錯。我爲某些頂點插入了特殊處理（僅在一個方向上有效），並在其他實現中忘記了這一點。

但 IM仍然比嚇一跳的是Dijkstra算法可以通過下列變化顯着加速：一般而言，Dijkstra算法包含了像一個循環：

MyListType toDoList; // List sorted by smallest distance 
InsertAllNodes(toDoList); 
while(! toDoList.empty()) 
{ 
    MyNodeType *node = *toDoList.first(); 
    toDoList.erase(toDoList.first()); 
    ... 
}

如果你改變了這點，它工作原理相同，但性能更好：

MyListType toDoList; // List sorted by smallest distance 
toDoList.insert(startNode); 
while(! toDoList.empty()) 
{ 
    MyNodeType *node = *toDoList.first(); 
    toDoList.erase(toDoList.first()); 
    for(MyNeigborType *x = node.Neigbors; x != NULL; x++) 
    { 
     ... 
     toDoList.insert(x->Node); 
    } 
}

看來，這種修改減少了不是大小的順序運行，但指數的順序。它將我的運行時窗體縮短爲30秒，小於2.在任何文獻中找不到此修改。這也很清楚，原因在於排序列表。插入/擦除的表現要差得多，因爲有100000個元素可以滿足要求。

答：

很多谷歌上搜索，我發現我自己的了。答案很清楚： boost graph lib。令人驚歎的 - 我還沒有發現這一段時間。如果您認爲Dijkstra實現之間沒有性能差異，請參閱wikipedia。

來源

2009-06-02 RED SOFT ADAIR

+26

我的一個朋友可以在3分鐘內用C++實現Dijkstra。我還沒有聽說過任何更快的實施。 – jbasko 2009-06-02 07:39:55

我建議你可能想檢查那些實現......如果它們是正確的，它們應該都返回相同的最短路徑... Dijkstra的算法不是啓發式的... – jerryjvl 2009-06-02 07:45:28

最短路徑的差異可能是使用雙精度數學時，由於求和長序列的雙精度時的舍入誤差。不同的求和順序可能會產生不同的錯誤。你能測試你的整數實現嗎？ – 2009-06-02 08:22:15

已知道路網絡（> 100萬個節點）的最佳實施方式的查詢時間爲微秒秒。請參閱第9次DIMACS實施挑戰（2006）的詳細信息。請注意，這些並不是簡單的Dijkstra，因爲整個過程要更快地獲得結果。

來源

2009-06-02 10:43:37 MSalters

這將取決於很多事情。你對輸入數據有多少了解？它是密集的還是稀疏的？這將改變算法的哪個版本是最快的。

如果它很密集，只需使用矩陣。如果它稀疏，則可能需要查看更有效的數據結構以查找下一個最近的頂點。如果你有更多關於你的數據集的信息而不僅僅是圖連通性，那麼看看不同的算法是否會像A *一樣更好地工作。

問題是，算法沒有「最快」版本。

來源

2009-06-02 07:49:59

最後一次檢查時，Dijkstra算法返回一個最優解。 Dijkstra's的所有「真實」實現應該每次返回相同的結果。類似地，漸近分析表明，隨着輸入大小的增加，對特定實現的次優化不會顯着影響性能。

來源

2009-06-02 07:59:28 Nick

可能是我沒有回答你的問題。我的觀點是，爲什麼在爲您的問題提供更高效的算法時使用Dijkstra。如果你的圖滿了三角形屬性（這是一個歐幾里德圖）

| ab | + | BC | > | ac |

（從節點a到節點b的距離加上從節點b到節點c的距離大於從節點a到節點c的距離），則可以應用A *算法。這個算法非常高效。否則，請考慮使用啓發式。實施不是主要問題。要使用的算法很重要。

來源

2009-06-02 08:18:18 Luixv

我想提出以下兩點： 1）Dijkstra vs A * Dijkstra算法是一種動態規劃算法，不是啓發式算法。 A *是啓發式的，因爲它也使用啓發式函數（讓h（x））來「估計」x點到終點的距離。這些信息在隨後決定下一步探索的節點中被利用。

對於諸如歐幾里德圖的情況，A *可以很好地工作，因爲啓發式函數很容易定義（例如，可以簡單地使用歐幾里得距離）。但是，對於非歐幾里得圖，定義啓發式函數可能會更困難，而錯誤的定義可能會導致非最優路徑。

因此，dijkstra比A *具有優勢，它適用於任何通用圖形（除了A *在某些情況下速度更快）。很可能某些實現可以互換使用這些算法，從而產生不同的結果。

2）dijkstra算法（和其他諸如A *）使用優先級隊列來獲取下一個要探索的節點。一個好的實現可以使用堆而不是隊列，更好的實現可以使用斐波那契堆。這可以解釋不同的運行時間。

來源

2017-04-21 18:22:08 eddykent

什麼是你知道的最快的Dijkstra實現（用C++）？

回答

相關問題