本科经典算法Dijkstra，被证明是普遍最优了：最坏情况性能也最优！

807 0 0

文章摘要

【关键词】 Dijkstra算法、最短路径、堆数据结构、算法优化、图算法

Dijkstra算法，自1956年由荷兰计算机科学家Edsger Dijkstra提出以来，一直是解决最短路径问题的经典算法。近日，这一算法取得了新的突破，被证明具有普遍最优性，即无论面对多么复杂的图结构，都能在最坏情况下达到理论上的最优性能。这一成果是学术界首次将普遍最优性概念应用于任何序列算法，由苏黎世联邦理工、CMU、普林斯顿等顶尖高校的科研人员共同完成，并将获得理论计算机顶会FOCS 2024的最佳论文奖。

Dijkstra算法在计算机科学和日常生活中有着广泛的应用，如谷歌地图、苹果地图中的最优路线计算，计算机网络中的路由协议，以及通信网络设计、机器人路径规划和物流运输优化等领域。算法的核心是使用堆数据结构，通过不断探索当前距离最短的路径，更新每个节点的最短距离，直到所有节点的距离都确定下来。

此次研究的突破在于对堆数据结构的改进。研究人员发现，尽管Fibonacci堆等常用数据结构在理论上具有较好的最坏情况时间复杂度，但在实际应用中未能充分利用图的局部结构特性，导致在处理某些类型的图时计算代价高昂。为此，研究人员提出了一种全新的堆数据结构，具备特殊的“工作集属性”，能够充分利用操作的局部性，优先处理最近插入的元素，降低提取最小元素的成本。这种改进使得Dijkstra算法在具有局部性特征的图上表现出色，具备了普遍最优性。

此外，这项研究还提供了精确的复杂度分析，证明了Dijkstra算法在具有工作集属性的堆上的比较次数是O(OPTQ(G)+n+max⁡w∈WG∣FG,w∣)，其中OPTQ(G)是解决距离排序问题的最优算法所需的比较次数，n是顶点数，∣FG,w∣是前向边的数量。这一成果不仅推动了图算法的研究，也为实际应用中的算法设计提供了新的视角和工具。