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