最短路径算法Dijkstra被ETH证明普遍最优！最坏情况都有最优解！权威发布！

0. 论文信息

标题：Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps

作者：Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan, Jakub Tětek

机构：ETH Zurich、Carnegie Mellon University、Princeton University、BARC

原文链接：https://arxiv.org/abs/2311.11793

1. 导读

本文证明了当与足够有效的堆数据结构结合时，Dijkstra的最短路径算法在运行时间和比较次数上都是普遍最优的。泛最优性是对图算法的强大的超越最坏情况的性能保证，它非正式地陈述了单个算法对于每个单个图拓扑尽可能好地执行。我们把这一概念首次应用于任何顺序算法。我们设计了一个新的堆数据结构，其工作集属性保证了堆在堆操作中利用了局部性。我们的堆匹配Fibonacci堆的最佳(最坏情况)界限，但也提供了超越最坏情况的保证，即提取最小元素的成本仅仅是在它之后插入的元素数量的对数，而不是堆中所有元素数量的对数。这使得提取最近添加的元素更便宜。我们证明了我们的工作集性质足以保证泛最优性，特别是对于根据顶点与源顶点的距离对顶点进行排序的问题:在固定拓扑上运行Dijkstra算法所生成的堆操作序列中的局部性足够强，以至于可以将任何堆使用我们的工作集性质所执行的比较次数与解决该拓扑上的距离排序问题所需的最小比较次数相结合。

2. 引言

普适最优性（Universal Optimality）是图算法的一种强大性能保证，超越了最坏情况，非正式地表述为：单个算法在每种图拓扑结构上都能以尽可能快的速度运行。

本文首次将这一概念应用于标准的顺序计算模型。我们证明，当与足够高效的堆数据结构相结合时，Dijkstra算法在自然问题——按节点到源点的距离排序——上具有普适最优性。

其次，我们为此结果设计了一个足够高效的堆。我们的新堆是对Fibonacci堆的严格改进，它在保证ExtractMin操作的超越最坏情况属性的同时，保持了Insert和DecreaseKey操作的复杂度恒定。

具体来说，我们发现Iacono先前提出的堆的自然工作集属性足以保证Dijkstra算法的普适最优性。粗略地说，工作集属性保证从堆中提取最小元素的成本是对该元素之后插入的元素数量的对数，而不是堆中所有元素数量的对数（精确定义稍强）。

我们的普适最优性结果表明，这一属性与Dijkstra算法之间存在着惊人的清晰相互作用：任何具有工作集属性的堆都能使算法高效地利用其操作的图的每一个结构属性，达到任何基于比较的算法所能达到的最大程度。

我们还提出了一种Dijkstra算法的变体，它在时间复杂度和进行的比较次数方面都具有普适最优性。我们注意到，虽然Dijkstra算法在任何图上的时间复杂度都位于相对较窄的Ω(m+n)和O(m+n log n)范围内，但按节点距离排序所需的比较次数可以小至0。

除了我们在Dijkstra算法中的应用外，我们希望本文能为未来在标准顺序计算模型中应用（普适最优性的变体）解决问题的研究开辟道路。

3. 超越最坏情况：普适最优性

渐近最坏情况复杂度的概念是理论计算机科学和算法设计的关键概念、成就和基石。随着领域的成熟和理解的深化，越来越多的先进算法基本上达到了最坏情况下可实现的最佳性能。然而，这些保证可能并不令人满意——仅仅因为存在一些无法表现良好的实例（或实例族），并不意味着人们应该满足于在任何简单实例上也表现同样糟糕。

参数化复杂度领域设定了寻找输入x的某个参数θ(x)的目标，并给出了相对于输入大小|x|和θ(x)都具有良好复杂度的算法。在最好的情况下，人们可能得到一个相对于|x|和θ(x)都是最优的算法——即，在这种参数化下，没有正确的算法具有更好的复杂度。

将参数化算法推向极端，可以将θ(x)设为x，即按实例本身进行参数化。这导致了一个称为实例最优性的概念。在这种参数化下最优的任何算法在任何单个输入上至少与任何正确的算法一样好。

遗憾的是，实例最优算法很少存在。然而，在加权图的图算法中常用的一种替代方法是普适最优性。在普适最优性中，如果我们按图G进行参数化，而不是按权重w进行参数化，我们希望算法A是最优的。也就是说，对于任何图G和任何其他正确的算法A′，A在G上所有可能权重下的最坏情况运行时间渐近地不比A′在所有可能权重下的最坏情况运行时间差。

从直观上讲，普适最优算法在任何给定的图拓扑结构上都能以尽可能快的速度运行。例如，如果存在针对平面图的快速算法，那么普适最优算法在任何平面图上运行时都必须很快。这里的平面图可以替换为任何其他图的子类，甚至具体的图。

4. 我们的结果：具有工作集属性的堆实现的Dijkstra算法的全局最优性

我们现在将讨论当Dijkstra算法使用具有工作集属性（一种超越最坏情况的特定属性）的堆时，如何使其达到全局最优。

Dijkstra算法的全局最优性。Dijkstra算法解决了与最短路径相关的一系列问题：它计算从源节点到所有节点的距离，找到最短路径树，甚至返回按距离排序的节点顺序。众所周知，Dijkstra算法在使用Fibonacci堆时的时间复杂度O(m+n log n)是“最佳的”。但为了使这一说法精确，我们需要做出两个承诺：首先，我们需要在比较模型的类似物中工作。其次，我们需要考虑一个包括按距离排序节点任务的问题；只有这样，我们才能论证时间复杂度中的O(n log n)项无法改进，因为星形图上的距离排序问题等价于排序问题。

我们采用相同的方法，并在本文中始终考虑以下问题。

定义1.1（距离排序问题（DO））。给定一个具有n个节点的有向图G，一个起始节点s，以及m条具有长度的边，按它们从s的距离递增顺序输出G的所有顶点。

我们证明，如果Dijkstra算法使用来自定义1.4的具有某种超越最坏情况属性的优先队列，则它对于距离排序问题是全局最优的。

定理1.2。在比较加法模型中，使用任何具有工作集属性的类似Fibonacci的优先队列实现的Dijkstra算法，在运行时间方面对于距离排序问题是全局最优的。这既适用于有向图也适用于无向图，并且与确定性和随机性算法相比都是如此。

因此，Dijkstra算法对于不仅要求我们计算节点顺序，还要求我们计算最短路径树或距离的问题也是全局最优的。

我们提出了一种技术上更复杂的算法，该算法不仅在时间复杂度方面实现了全局最优性，而且在比较次数方面也实现了全局最优性。

最后，我们证明了优先队列的几种自然实现（例如标准Fibonacci堆或伸展树）并不能导致Dijkstra算法的全局最优性。

具有工作集属性的优先队列。我们的技术贡献之一是确定了优先队列的工作集属性是暗示Dijkstra算法全局最优性的正确属性。工作集的定义在二叉搜索树的文献中是众所周知的，而对于堆，它首次出现在Iacono的工作中。接下来给出定义，并在图1中进行说明。

定义1.3（工作集。考虑任何支持插入（Insert）和提取最小值（ExtractMin）操作的优先队列。对于数据结构中存在的元素x，我们定义其工作集如下。

对于x插入和提取之间的每个时间步t，我们定义x在时间t的工作集为在x之后插入且在时间t仍然存在的元素集合Wx,t。我们将x本身包含在Wx,t中。

我们固定任何使|Wx,t|的值最大化的时间t0；我们称集合Wx,t0为x的工作集，并用Wx表示。

举个例子：对于堆中插入的第一个元素x1，其工作集的大小等于x1插入和提取之间堆的最大大小。对于任何后来插入的元素x2，其工作集大小的定义类似，但x2之前插入的元素“不计入”。

我们设计了一种数据结构，通过具有以下工作集属性来改进Fibonacci堆。

定义1.4（具有工作集属性的类似Fibonacci的优先队列）。我们说，如果一个数据结构支持以下操作，并且对于任何操作序列，它们的摊销时间复杂度如下，则该数据结构是具有工作集属性的类似Fibonacci的优先队列：插入（Insert）、查找最小值（FindMin）和减小键（DecreaseKey）在O(1)内，提取最小值（ExtractMin）在O(1 + log |Wx|)内，其中Wx是被提取元素的工作集。

定理1.5。存在一个具有工作集属性的类似Fibonacci的优先队列。

我们认为定理1.5具有独立的意义。我们还在定理4.9中展示了如何通过将某些操作的复杂性中的log log n损失从摊销情况变为最坏情况来进一步加强它。

5. 直觉与技术

在本节中，我们首先讨论来自图2的示例图G1以促进理解。然后，我们总结我们的结果的证明。

示例。考虑来自图2的图G1，其中叶子节点数t < n/2。首先，让我们计算在该图上使用工作集的Dijkstra算法的时间复杂度：除了一个加性的O(n)项外，时间复杂度主要由ExtractMin操作决定。节点u1, . . . , ut, v1的工作集大小为O(t)，而节点v2, . . . , vr（其中r = n − t − 1）的工作集大小都为1。因此，该算法的复杂度为O(n + t log t)。

为了看到这对于G1是最佳的，请注意按它们从s的距离对节点u1, . . . , ut进行排序的问题等价于对t个数进行排序的问题，这在比较模型中需要Ω(t log t)的时间。此外，任何算法都需要Ω(m + n) = Ω(n)的时间来读取输入。

我们的主要定理定理1.2简单地表明，对于所有图，具有工作集属性的Dijkstra算法的时间复杂度与该图的最佳下界相匹配。

为了理解这一结果，请考虑以下针对G1量身定制的、非常不同的算法。该算法从线性顺序s < v1 < · · · < vn−t−1开始，并反复使用二分搜索将节点ui插入到这个顺序中。这样的算法具有O(n + t log n) = O(n + t log t)的复杂度，即它对于图G1也是最佳的。定理1.2表明，具有工作集属性的Dijkstra算法在与每个此类特定实例算法在每个图上相比时都是具有竞争力的。

全局最优性：定理1.2背后的直觉。除了一个加性的O(m + n)项外，Dijkstra算法的时间复杂度主要由其ExtractMin操作的复杂度决定。这些操作的复杂度又由相应工作集的大小决定。

为了证明在给定图G上使用工作集的Dijkstra算法的最优性，我们仔细构造了一个在G上的权重上的下界分布，该分布“隐藏”了许多排序问题的实例。更具体地说，对于任意图G及其权重w，考虑在(G,w)上运行Dijkstra算法。回想一下，Dijkstra算法维护一个优先队列，并且任何节点v ∈ V(G)都恰好进入和离开该队列一次；在任何时间点，优先队列包含处于算法“探索边界”上的节点，并且这个探索边界将图分为两部分——已经看到的和尚未看到的顶点。

考虑在整个算法运行过程中具有最大工作集Wu的节点u。

观察到，对于时间t，当Wu = Wu,t时，Wu恰好是Dijkstra算法在时间t时的探索边界中的节点集合（如果边界上存在某个v不属于Wu，则Wu ∪ {v} ⊆ Wv，这与Wu的最大性相矛盾）。

关键的观察结果是，我们可以局部改变进入Wu的边的权重w，从而获得权重wu的分布，该分布具有以下性质：如果我们根据在权重wu下与s的距离对Wu中的节点进行排序，则它们的顺序是一个均匀随机的排列。也就是说，实例(G,wu)“嵌入”了一个排序问题，该问题需要Ω(|Wu| log |Wu|)的时间来解决。

另一方面，由|Wu|的最大性我们知道，我们的算法在Wu中的节点上执行ExtractMin操作的总时间最多为O(|Wu| log |Wu|)。

也就是说，通过wu，我们成功地为Wu中的节点“付费”：在(G,w)中，Dijkstra算法在它们上花费的时间（最多相差一个常数）与从(G,wu)中采样的实例中任何正确算法平均需要花费在它们上的时间相同。

定理1.2的其余证明部分归结为论证我们可以继续这个过程，直到整个图被分离成我们称之为屏障序列的部分。这样，我们最终构造了一个为所有ExtractMin操作“付费”的下界分布w。

让我们通过展示如何选择第二个屏障（见图3）来解释这是如何做到的。

在选择屏障Wu之后，我们继续在V (G) \Wu中找到具有最大工作集W′u = W′u,t′的节点u′，其中我们定义W′v为在不计算工作集定义中的Wu节点时v的工作集。

现在有两种情况，取决于t′ > t还是t′ < t。重要的是，在第一种情况下，W′u′中的所有节点都“在”Wu的节点“之后”，而在另一种情况下，所有节点都“在”之前。这一性质最终使我们能够构造一个下界分布，该分布为Wu和W′u′都嵌入了排序下界。

在t′ < t的情况下，我们遇到了一个额外的问题：集合W′u′可能远小于集合Wu′，因此Ω(|W′u′ | log |W′u′ |)的下界可能无法支付相应的ExtractMin成本O(Σv∈W′u′ log |Wv|)。为了解决这个问题，我们限制了由于从图中去除Wu而导致的工作集大小总体减少的上界。特别是，我们分析了：

如果我们仅移除Wu中的任意一个节点，而不是一次性移除整个集合，工作集大小会发生多大的变化？每个工作集的大小最多只能减少一个，但在u插入之前插入的许多节点的工作集大小都可能减少一个。我们将工作集大小减少的节点称为v1, ..., vk，并根据它们的插入时间从大到小进行排序（见图3）。我们注意到，每个vi只有在u插入之后才被提取，否则其工作集大小不会减少。这意味着，由于vi在u插入时的大小即为如此，因此每个vi的工作集大小至少为|Wvi| ≥ i + 1。在最坏的情况下，移除u会导致log |Wv1|从log 2变为log 1，log |Wv2|从log 3变为log 2，以此类推。通过观察一个折叠求和，我们注意到，按照方程（1）的意义，工作集大小的整体减少量最多为log |Wvk|，根据我们对u的最大性的假设，这最多为log |Wu|。

回顾一下，上述分析是在移除Wu中任意一个节点的情况下进行的。因此，在逐一移除Wu中的所有节点后，我们可以将方程（1）的表达式上限设为O(|Wu| log |Wu|)。这是非常幸运的：我们可以让第一个屏障Wu支付由W和W'之间的不匹配导致的未来所有下界和上界之间差距的费用。 推荐课程： 面向三维视觉的Linux嵌入式系统教程[理论+代码+实战] 。

现在，我们可以继续这个过程，直到整个图G被分解成一个屏障序列。然后，我们可以直接定义一个下界分布w，它将排序下界嵌入到每个屏障中。

工作集属性：定理1.5背后的直觉。接下来，我们讨论具有工作集属性的堆的构建。我们的构建是一个通用的黑盒构建，它使用任意优先级队列（如斐波那契堆）来创建一个新的堆，该堆具有相同的保证，并且额外满足定理1.5中的工作集属性。

该构建背后的主要思想简单明了，并且已出现在文献中：我们维护一个堆列表，其中第i个堆的大小最多为2i。每当插入一个新元素时，我们将其插入到最小的堆中；我们将保持一个不变性，即较大的堆包含比较小的堆更旧的元素。每当一个堆变得过大时，我们就按如下方式递归地将其与较大的相邻堆合并。

一般来说，考虑第i个堆Hi。在合并过程中，一个新的进位堆C从位置i-1的合并中到达，我们检查Hi和C中的元素总数是否最多为2i。如果是，我们将两个堆合并在一起并完成合并过程。否则，C将替换Hi成为新的第i个堆，而Hi将成为下一个（i+1）级的新的进位堆。注意，每当堆Hi“升级”到下一个位置i+1时，我们知道在刚替换Hi和较小堆Hi-1的原始进位堆C中至少有2i-1个元素。否则，就不会触发第i级的合并。这意味着每个新升级到位置i+1的元素的工作集大小至少为2i-1。这个观察结果通过归纳法意味着Hi中的每个元素的工作集大小为Ω(2i)。另一方面，由于Hi最多有2i个元素，因此从Hi中提取的成本为O(1 + log 2i)。因此，我们可以将提取成本写为O(1 + log |Wx|)，这是所需的。

注意，第i个堆的大小不必大约为2^i，其大小最多可以为2^2i以使我们的论证成立，并且在第4节的正式构建中，我们也选择了这种双指数方法。

还有一些技术细节需要解决。例如，为了提取最小元素，我们首先需要找出哪个堆包含它。如果我们选择堆的大小以双指数方式增长，那么我们最多有O(log log n)个堆，因此我们可以将它们的最小值维护在一个单独的堆中，这会导致额外的O(log log log n)损失。虽然这种损失已经很小，但我们表明，通过仔细的数据结构，我们可以使构建中的开销忽略不计，并恢复与原始堆相同的渐近保证。

扩展到比较。本文最具技术挑战性的部分是将我们的主要结果定理1.2扩展到比较复杂度，它衡量我们的算法需要多少比较问题的答案。例如，如果图G是一条路径，s是其叶子节点，则距离排序问题的比较复杂度实际上为0，因为我们根本不需要访问图的权重就可以确定节点的排序方式！

我们在第5节中表明，存在一个算法同时在这两种复杂度度量下都是普遍最优的。具有工作集属性的Dijkstra算法本身并不是这样的算法：在图2上，其比较复杂度为Ω(t log t + n)，而最优比较复杂度仅为O(t log n)。然而，通过查看我们对Dijkstra算法的分析，我们可以注意到，它在比较复杂度方面“几乎”是普遍最优的——主要问题是，在我们的下界构建中，我们可能会在一个节点上嵌入一个排序问题。对一个数字进行排序的比较复杂度为0，而算法使用了Θ(1)个操作，这在上界和下界之间产生了不匹配。这促使我们提出了最终的算法，该算法使用具有工作集属性的Dijkstra算法作为子程序。具体来说，在我们的最终算法中，我们首先使用0个比较查询仔细收缩输入图。然后，我们使用具有工作集属性的Dijkstra算法在该收缩图上解决单源最短路径问题（SSSP），并将找到的最短路径树还原到原始图上。

这样，我们就解决了SSSP问题，而不是距离排序问题。幸运的是，对于树来说，还有一个基于动态规划的不同且普遍最优的距离排序算法。最后，我们将这个算法应用于找到的最短路径树。

我们应该如何收缩我们的图？如果它是无向的，收缩桥就足够了，但当图是有向的时，我们需要找到一种更复杂的结构，称为支配树。

6. 总结 & 开放问题

总体而言，看到通用最优性和实例最优性概念在更多场景中的应用将是非常有意思的。在此，我们提出一个我们认为有趣的具体未解问题。

通用最优最小生成树（MST）。在比较模型中，是否存在针对最小生成树（MST）问题的确定性通用最优算法？我们注意到，根据Chazelle [Cha00]的研究成果，MST的确定性复杂度已经非常接近线性（达到逆Ackermann函数）。此外，Pettie和Ramachandran [PR02]的研究成果提供了一个明确的渐近最优MST算法，其适用于最坏情况。然而，如何利用他们的方法实现通用最优性尚不清楚：他们的算法利用了以下思想，即如果我们能在O(OPT(m, n))时间内，将具有m条边和n个顶点的图中MST的计算问题简化为在具有m/2条边和n/2个顶点的图中MST的计算问题，那么我们就可以通过递归在O(OPT(m, n))时间内完全解决MST问题。如果我们想要实现通用最优性，这一推理路线似乎并不适用。

对更多实验结果和文章细节感兴趣的读者，可以阅读一下论文原文~

本文仅做学术分享，如有侵权，请联系删文。

3D视觉交流群，成立啦！

目前我们已经建立了3D视觉方向多个社群，包括 2D计算机视觉 、 最前沿 、 工业3D视觉 、 SLAM 、 自动驾驶 、 三维重建 、 无人机 等方向，细分群包括：

工业3D视觉 ：相机标定、立体匹配、三维点云、结构光、机械臂抓取、缺陷检测、6D位姿估计、相位偏折术、Halcon、摄影测量、阵列相机、光度立体视觉等。

SLAM ：视觉SLAM、激光SLAM、语义SLAM、滤波算法、多传感器融合、多传感器标定、动态SLAM、MOT SLAM、NeRF SLAM、机器人导航等。

自动驾驶：深度估计、Transformer、毫米波|激光雷达|视觉摄像头传感器、多传感器标定、多传感器融合、自动驾驶综合群等、3D目标检测、路径规划、轨迹预测、3D点云分割、模型部署、车道线检测、Occupancy、目标跟踪等。

三维重建 ：3DGS、NeRF、多视图几何、OpenMVS、MVSNet、colmap、纹理贴图等

无人机 ：四旋翼建模、无人机飞控等

2D计算机视觉