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

时隔近70年，阿谁用来惩办最短旅途问题的经典算法——Dijkstra，咫尺有了新碎裂：

被阐明具有无数最优性（Universal Optimality）。

什么酷爱酷爱？

这就意味着不管它靠近多复杂的图结构，即便在最坏情况下皆能达到表面上的最优性能！

而况这如故学术界初度将这一见解应用于任何序列算法。

△图源：Quantamagzine

对于Dijkstra算法，想必好多东谈主敬佩不会目生，毕竟它是每个计算机本科生必学的内容。

而况从它设立于今，依然活着俗地应用于咱们的泛泛生活中，举例在谷歌舆图、苹果舆图，Dijkstra算法就被用来计算从用户刻下位置到指标地的最优路子。

在计算机收罗中，被世俗应用于路由公约中；举例绽放最短旅途优先（OSPF）公约即是基于Dijkstra算法来计算收罗中数据包的最优传输旅途。

再如通讯收罗遐想、机器东谈主旅途筹画和物流运输优化等界限，亦然处处皆有它的身影。

（干系教程可参考：https://www.youtube.com/watch?v=EFg3u_E6eHU）

而这项汇注了苏黎世联邦理工、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（1 + 1 = 2）。更新已知的最短旅途。纪录新的最短旅途：在探索历程中发现更短的旅途时，更新纪录。举例，A到C的原始距离是5，但通过B和D的旅途到C的总距离是3（1 + 1 + 1 = 3），比本来的距离短，因此更新A到C的距离为3。叠加风光，直到袒护系数点：算法连续遍历，直到系数节点的最短旅途皆被笃定。每次优先继承距离最短的旅途进行下一步计算，逐渐优化到每个点的最短旅途。

△图源：Quantamagzine

最终，Dijkstra算法不错快速找到收罗中从肇始点到其他系数节点的最短旅途。

在起初的Dijkstra算法论文中使用到了一个通俗且关键的数据结构——堆（Heap），而这就为自后的计算机科学家们留住了改进的余步。

举例1984年，两位计算机科学家遐想了一种好意思妙的堆数据结构，使得Dijkstra算法在惩办单源最短旅途问题所需的时候上达到了表面极限或“下限”。

从某种特定酷爱酷爱上说，这个版块的Dijkstra算法依然不错说是最好的，亦然近40年来的一种“圭臬”。

而此次的最新论文，接头东谈主员的碎裂口依旧是这个堆数据结构。

因为他们发现，像Fibonacci堆等常用的数据结构固然在表面上具有较好的最坏情况时候复杂度（Worst-case time complexity），但在很厚情况下未能充分应用图的局部结构特色。

这就导致在处理某些类型的图时，仍然需要腾贵的计算代价。

但如果在1984年遐想的堆基础上加入对最近插入项快速探听的智力，就不错显贵进步算法的效力。

为此，接头东谈主员提议了一种全新的堆数据结构——具备特等的 “责任集属性”（Working Set Property）。

所谓 “责任集属性” ，指的是堆大约充分应用操作的局部性，从而优先处理最近插入的元素，裁减索要最小元素的老本。

这个见解访佛于咱们在不休待服务项时，会优先处理那些刚刚添加的伏击任务，从而更高效地完成责任。

淌若用公式化的表述，就如下图所示。

对于在堆中插入并随后被索要的恣意元素x，其责任集Wx包括了在x被插入后、在x被索要前插入的系数元素，以及x本人。

借助这种“责任集属性”，新遐想的堆数据结构大约显贵进步Dijkstra算法的举座性能，尤其是在具有局部性特征的图上。

也得胜使Dijkstra算法具备了无数最优性，不仅在最坏情况下具有最优性，还能在职何图结构上弘扬出色。

不仅如斯，这项责任还提供了精准的复杂度分析。

举例，作家阐明了Dijkstra算法在具有责任集属性的堆上的比拟次数是O(OPTQ(G)+n+max⁡w∈WG∣FG,w∣)。

其中，OPTQ(G)是惩办距离排序问题的最优算法所需的比拟次数，n是极点数，∣FG,w∣是前向边的数目。

这也为算法的性能提供了更精准的界限。

一言以蔽之，这些效力不仅鼓励了图算法的接头，也为本色应用中的算法遐想提供了新的视角和器具。

喝咖啡时设立的算法

对于Dijkstra算法设立的故事，其实是始于一次偶然的灵感。

1956年，年仅26岁的荷兰计算机科学家Edsger Dijkstra其时正试图为一台新式计算机ARMAC编写一个范例，来展示它的计算智力。

有一天，他和光棍妻在阿姆斯特丹购物时走进了一家咖啡馆，恰是在休息的已而中，Dijkstra骤然有了灵感，想出了一个计算最短旅途的算法。

在莫得纸和笔的情况下，他花了大致20分钟在脑海中推上演了这个算法的细节。

正如他在晚年一次采访中所说的那样：

莫得纸笔的情况下，你简直被动幸免系数不错幸免的复杂性。

也恰是这种轻易和优雅，使得Dijkstra算法在随后的几十年里成为计算机科学界限的经典。

Edsger Dijkstra不错说是一位极具影响力的计算机科学家，他不仅以其最短旅途算法著名，还对计算机科学的许多基础界限作念出了创始性的孝敬。

Dijkstra出身于1930年，父亲是一位化学家，母亲是一位出色的数学家。

1951 年，Dijkstra在父亲的建议下前去剑桥进入了一门为期三周的编程课程，此次资格蜕变了他的工作轨迹。

在此时期，他遭遇了著名的数学家和计算机科学家Adriaan van Wijngaarden，并由此取得了在阿姆斯特丹数学中心（Mathematical Centre）的责任契机。

Dijkstra是荷兰首位以“范例员”身份被雇佣的东谈主，1956年完成学业后，他连续在数学中心责任，并于1959年发表了他的著名论文A Note on Two Problems in Connexion with Graphs。

这篇论文先容了他提议的最短旅途算法，自后成为了计算机科学中援用次数最多的论文之一。

尽管Dijkstra的算法十分优雅，但其时简直莫得计算机科学期刊，发表历程十分周折，最终他继承将其发表于新创刊Numerische Mathematik上。

Dijkstra在工作生计中赢得了极高的声誉，并于1972年取得计算机科学界限最负着名的图灵奖。

他不仅在编程言语、操作系统和并发戒指等界限作念出了许多基础性孝敬，还以其对编程要领学的深刻想考而著称。

他强调范例的正确性，以为范例应该从一运行就正确地遐想，而不是通过调试来达到正确。

不外与此同期，Dijkstra的性情也特别特有，他既被歌咏也被品评，是一位充满争议的东谈主物。

他对于计算机科学的解说和接头有着浓烈的不雅点，每每发表极具挑战性的言论。

举例，他反对使用goto语句，并在1968年发表了著名的著作Go To Statement Considered Harmful，这篇著作激发了世俗的争议，但最终他的不雅点得到了无数认同。

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开云kaiyun