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

正文： 金磊 发自 凹非寺 量子位 | 公众号 QbitAI

Dijkstra算法，用于解决最短路径问题，历经近70年后被证明具有普遍最优性，无论面对何种复杂图结构，都能在最坏情况下达到理论最优性能。这是学术界首次将这一概念应用于任何序列算法。

Dijkstra算法是每位计算机本科生必学内容，已在日常生活中广泛应用，如谷歌地图和苹果地图计算最优路线。它还在计算机网络中用于路由协议，在通信网络设计、机器人路径规划和物流运输优化等领域也常见其身影。

这项研究由苏黎世联邦理工、CMU、普林斯顿等高校科研人员合作完成，该算法被证明是解决单源最短路径问题的“近乎理想”方法。这项研究通过改进堆数据结构，引入“工作集属性”，显著提升了Dijkstra算法的性能，尤其适用于具有局部特性的图结构。

Dijkstra算法的突破在于堆数据结构的改进，使其能在处理某些类型图时减少计算成本。研究者发现，新设计的堆数据结构能够更好地利用图的局部特性，从而提高算法效率。该研究成果将在理论计算机顶会FOCS 2024上获得最佳论文奖。

Dijkstra算法诞生于1956年，源于Edsger Dijkstra的一次灵感。当时他正在为新型计算机ARMAC编写程序，灵感来自一次咖啡馆休息时的思考。这一算法因其简洁和高效，成为计算机科学的经典之作。Dijkstra不仅发明了这一算法，还在编程语言、操作系统和并发控制等领域做出了重要贡献。

Dijkstra算法的核心思想是不断探索当前距离最短的路径，更新每个节点的最短距离，直到所有节点的距离都确定下来。麻省理工学院的计算机科学家Erik Demaine曾评论，这是一个伟大且高效的算法。

论文地址：https://arxiv.org/abs/2311.11793

参考链接： [1] https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/ [2] https://inference-review.com/article/the-man-who-carried-computer-science-on-his-shoulders