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）。