Dijkstra 演算法

Dijkstra 演算法是一種用於查詢圖測地線的演算法，即圖中兩個圖頂點之間的最短路徑。它的功能是透過構建從初始頂點到圖中每個其他頂點的最短路徑樹來實現的。

該演算法在 Wolfram 語言中實現為FindShortestPath[g,Method -> "Dijkstra"].

在具有 個節點和 條邊的圖上，Dijkstra 演算法的最壞情況執行時間為 ，因為它允許有向環。它甚至可以找到從源節點 到圖中所有其他節點的最短路徑。這基本上是節點選擇的 和距離更新的 。雖然 是稠密圖的最佳可能複雜度，但對於稀疏圖，複雜度可以顯著提高。

透過稍微修改，Dijkstra 演算法可以用作反向演算法，為匯聚節點維護最小生成樹。透過進一步修改，它可以擴充套件為雙向演算法。

Dijkstra 演算法的瓶頸是節點選擇。但是，使用 Dial 的實現，對於稀疏圖可以顯著改進這一點。

在電視劇 NUMB3RS 第三季劇集 "Money For Nothing" (2007) 中，數學教授 Charlie Eppes 使用 Dijkstra 演算法來找到被劫持卡車逃離洛杉磯最可能的路線，該卡車裝載了數百萬美元的現金和醫療用品，以及兩名綁架受害者。

Haeupler等人 (2024) 證明，當 Dijkstra 演算法與足夠高效的 堆 資料結構結合使用時，無論是在執行時間還是比較次數方面都是普遍最優的。這一結果為圖演算法提供了強大的超越最壞情況效能保證。通俗地說，這意味著 Dijkstra 演算法對於每種可能的圖拓撲結構都表現得儘可能好（Haeupler等人，2024）。