本科经典算法Dijkstra，被证明是普遍最优了：最坏情况性能也最优！
什么意思？
这意味着，无论面对多复杂的图结构，哪怕在最坏情况下，它都能达到理论上的最优性能。
更关键的是，这还是学术界首次将这一概念应用于任何序列算法。
△图源：Quantamagzine
说到Dijkstra算法，想必每个计算机专业的学生都不会陌生，这几乎是必修课里的经典内容。
从诞生至今，它早已渗透到了我们日常生活的方方面面。比如你在谷歌地图或苹果地图上查路线，背后就有它在计算从当前位置到目的地的最优路径；在计算机网络中，它也是路由协议的核心，比如开放最短路径优先（OSPF）协议，就是基于它来计算数据包的最佳传输路径。此外，通信网络设计、机器人路径规划、物流运输优化……这些领域，也处处都有它的身影。
而现在，这项由苏黎世联邦理工、CMU、普林斯顿等顶尖高校研究人员共同完成的研究，让这个经典算法达到了一个前所未有的高度。
哥伦比亚大学计算机科学家Tim Roughgarden在看完论文后直言：
值得一提的是，这篇论文已经斩获了下周即将举办的理论计算机顶会FOCS 2024（计算机科学基础研讨会）的最佳论文。
一句话总结：现在的Dijkstra算法，已经被证明是解决单源最短路径问题的“近乎理想”的方法。
那么，这项研究究竟是如何实现突破的？
70年经典算法新突破
首先，我们还是通过一个简单的例子，快速回顾一下Dijkstra算法的基本原理。
如下图所示，Dijkstra算法寻找最短路径的过程，大致可以分为四步：
从起点出发：选择起点A。计算从A到邻近点的距离，比如到B是1，到C是5。先选较短的，也就是前往B。
继续探索：从新节点B继续查找邻近点的距离，并将这些距离加上从A到B的距离。比如从A到B是1，B到D是1，那么A到D的总距离就是2。同时，更新已知的最短路径。
记录新的最短路径：在探索过程中，如果发现更短的路径，就更新记录。比如A到C原来的距离是5，但通过B和D的路径到C的总距离是3（1+1+1=3），比原来的短，所以就把A到C的距离更新为3。
重复步骤，直到覆盖所有点：算法继续遍历，直到所有节点的最短路径都被确定下来。每次优先选择距离最短的路径进行下一步计算，逐步优化到每个点的最短路径。
△图源：Quantamagzine
最终，Dijkstra算法可以快速找到网络中从起始点到其他所有节点的最短路径。
在最初的Dijkstra算法论文中，用到了一个简单但关键的数据结构——堆（Heap）。而正是这个选择，为后来的计算机科学家们留下了改进的余地。
比如1984年，两位计算机科学家设计了一种巧妙的堆数据结构，使得Dijkstra算法在解决单源最短路径问题所需的时间上，达到了理论极限，或者说“下限”。从某种意义上说，这个版本的Dijkstra算法已经是最好的了，并且在近40年里一直被视为“标准”。
而这次的最新论文，研究人员的突破口，依然在这个堆数据结构上。
他们发现，像Fibonacci堆这些常用的数据结构，虽然在理论上具有较好的最坏情况时间复杂度，但在很多情况下，并没有充分利用图的局部结构特性。这就导致在处理某些类型的图时，仍然需要高昂的计算代价。
但如果能在1984年设计的堆基础上，加入对最近插入项快速访问的能力，就能显著提升算法的效率。
为此，研究人员提出了一种全新的堆数据结构——它具备特殊的“工作集属性”（Working Set Property）。
所谓“工作集属性”，指的是堆能够充分利用操作的局部性，优先处理最近插入的元素，从而降低提取最小元素的成本。打个比方，这就像我们管理待办事项时，会优先处理那些刚刚添加的紧急任务，这样能更高效地完成工作。
如果用公式化的表述，就如下图所示：
对于在堆中插入并随后被提取的任意元素x，其工作集Wx包括了在x被插入后、在x被提取前插入的所有元素，以及x本身。
借助这种“工作集属性”，新设计的堆数据结构能够显著提升Dijkstra算法的整体性能，尤其是在具有局部性特征的图上。这也成功让Dijkstra算法具备了普遍最优性——不仅在最坏情况下表现最优，还能在任何图结构上都有出色表现。
不仅如此，这项工作还提供了精确的复杂度分析。比如，作者证明了在具有工作集属性的堆上，Dijkstra算法的比较次数是O(OPTQ(G)+n+maxw∈WG∣FG,w∣)。这里的OPTQ(G)是解决距离排序问题的最优算法所需的比较次数，n是顶点数，∣FG,w∣是前向边的数量。这为算法的性能提供了更精确的界限。
总而言之，这些成果不仅推动了图算法的研究，也为实际应用中的算法设计提供了新的视角和工具。
喝咖啡时诞生的算法
关于Dijkstra算法诞生的故事，其实始于一次意外的灵感。
1956年，年仅26岁的荷兰计算机科学家Edsger Dijkstra，当时正试图为一台新型计算机ARMAC编写一个程序，来展示它的计算能力。
有一天，他和未婚妻在阿姆斯特丹购物时，走进了一家咖啡馆。正是在休息的片刻中，Dijkstra突然灵光一闪，想出了一个计算最短路径的算法。在没有纸和笔的情况下，他花了大约20分钟，在脑海中完整推演出了这个算法的细节。
正如他在晚年一次采访中说的那样：
正是这种简洁和优雅，让Dijkstra算法在随后的几十年里，成为了计算机科学领域的经典。
Edsger Dijkstra是一位极具影响力的计算机科学家。他不仅以其最短路径算法闻名，还对计算机科学的许多基础领域做出了开创性贡献。
Dijkstra出生于1930年，父亲是化学家，母亲是出色的数学家。1951年，他在父亲的建议下，前往剑桥参加了一门为期三周的编程课程。这次经历彻底改变了他的职业轨迹。期间，他遇到了著名的数学家和计算机科学家Adriaan van Wijngaarden，并由此获得了在阿姆斯特丹数学中心工作的机会。
Dijkstra是荷兰首位以“程序员”身份被雇佣的人。1956年完成学业后，他继续在数学中心工作，并于1959年发表了著名论文《A Note on Two Problems in Connexion with Graphs》。
这篇论文介绍了他提出的最短路径算法，后来成为了计算机科学中引用次数最多的论文之一。尽管算法本身十分优雅，但当时几乎没有计算机科学期刊，发表过程相当困难，最终他选择将其发表于新创刊的《Numerische Mathematik》上。
Dijkstra的职业生涯赢得了极高声誉。1972年，他获得了计算机科学领域最负盛名的图灵奖。他不仅在编程语言、操作系统和并发控制等领域做出了许多基础性贡献，还以其对编程方法学的深入思考而著称。他强调程序的正确性，认为程序应该从一开始就正确地设计，而不是通过调试来达到正确。
不过，Dijkstra的性格也非常独特，他既被赞赏也被批评，是一位充满争议的人物。他对计算机科学的教育和研究有着强烈的观点，常常发表极具挑战性的言论。比如，他反对使用goto语句，并在1968年发表了著名的文章《Go To Statement Considered Harmful》。这篇文章引发了广泛的争议，但最终他的观点得到了普遍认可。
Dijkstra算法不仅可以计算从起始点到一个目的地的最短路径，还能给出从起始点到所有其他节点的排序，这正是单源最短路径问题的解决方案。它的核心思想是不断探索当前距离最短的路径，更新每个节点的最短距离，直到所有节点的距离都确定下来。这种算法的简洁性和高效性，使其成为经典的路径规划工具。
麻省理工学院的计算机科学家Erik Demaine曾评论道：
不过，算法的成功不仅归功于其核心思想，还离不开数据结构的选择。在几十年的发展中，研究人员不断改进堆数据结构，使得算法的整体性能不断提升。而这一次，改良堆数据结构，可以说是再次立功了。
