Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin
cs.DS
2025-04-24
清华、斯坦福、马普所给出确定性O(m log^{2/3} n)算法,在比较-加法模型下求解带非负实数权的有向单源最短路,首次在稀疏图上打破Dijkstra的O(m+n log n)。
带非负权的有向图上,单源最短路(SSSP)的教科书算法是 Dijkstra。配上斐波那契堆或松弛堆,比较-加法模型下的时间是 O(m + n log n)。这个模型只允许对边权做比较和加法,每次单位时间,正好对应实数权、不能玩整数位运算的设定。
Dijkstra 会顺手给出按距离排好的顶点序。Haeupler、Hladík、Rozhoň、Tarjan、Tětek 证明:如果算法必须输出这个序,Dijkstra 已经最优,Ω(n log n) 的排序下界搬不走。可如果只要每个点的距离、不要这个序,无向图上 Duan、Mao、Shu、Yin 在 2023 年已经给出随机化 O(m √(log n log log n)),稀疏图上快于 O(n log n)。有向图一直没人跨过这条线。
排序壁垒在图算法里不是第一次被打破。最小生成树早有 O(m log log n) 再到随机线性,瓶颈路、单源非降路径也都低于排序。SSSP 的有向实数权这一格,1959 年到这篇之前,稀疏图上停在 Dijkstra。
把 Dijkstra 的堆和 Bellman-Ford 的「松弛 k 步、不用排序」拼进同一套分治。
Dijkstra 运行时,堆里是前沿 S:一个点 u 如果还不完备(当前估计 d̂[u] 仍大于真距离 d(u)),那它的最短路一定经过 S 里某个已经完备的点。每次取 S 里离源点最近的那个,这个点一定完备,再松弛它的出边。麻烦在于 S 有时有 Θ(n) 个点,反复取最小等于维护全序,Ω(n log n) 下不来。
关键操作是把前沿缩小。设当前要算所有距离小于上界 B 的点,Ũ 是 d(u)<B 且最短路经过 S 的点集。取 k = log^{Ω(1)} n,分两种情况:
算法不用动态维护 Dijkstra 那种会变的前沿,改成 log n / t 层的分治。参数取 k = ⌊log^{1/3} n⌋, t = ⌊log^{2/3} n⌋,递归深度 O(log^{1/3} n)。朴素实现每层每个前沿点仍要 Θ(t) 时间,人均还是 Θ(log n);只对 pivot 花这个钱,pivot 大约是前沿的 1/log^{Ω(1)} n,人均就降到 log n / log^{Ω(1)} n。
子问题叫做有界多源最短路 BMSSP。给定层号 l、上界 B、前沿 S(|S| ≤ 2^{lt}),并保证:每个不完备且 d(v)<B 的点,最短路都经过 S 里某个完备点。BMSSP 返回新上界 B' ≤ B 和点集 U,结束时 U 里的点全部完备。要么成功(B'=B,该算的都算完),要么因为工作量太大提前停(|U| = Θ(k · 2^{lt}),B'<B)。顶层调用 BMSSP(⌈log n / t⌉, {s}, ∞),|U| ≤ n 远小于 k n,只能走成功分支,所有点的最短路就齐了。
FindPivots 从 S 松弛 k 步得到 W。|W| 一旦超过 k|S| 就直接把整个 S 当 pivot 返回;否则在当前估计构成的森林里,把规模至少 k 的树根收成 pivot 集 P,|P| ≤ |W|/k。常数出度保证 |W| 超标时仍是 O(k|S|)。
还要一个部分排序结构,避免对整个前沿全排序。数据放在两串块状链表里,每块最多 M 个键值对,外加一棵平衡树维护块上界。支持三种操作:Insert 均摊 O(max{1, log(N/M)}),BatchPrepend 把一批保证更小的值插到最前,Pull 取出最多 M 个最小键并给一个分隔上界。每层 M = 2^{(l-1)t},Insert 均摊 O(t),BatchPrepend 每个点 O(log log n)。
图先变成常数度:每个点拆成零权环,原边接到环上对应位置,入度出度至多 2,顶点数和边数都是 O(m)。路径长度用「长度、跳数、反向顶点序列」做字典序打破平局,比较仍是 O(1),最短路树不会因为等长路径而坏掉。
这是一篇纯理论论文,没有实现,没有在真实图上的计时。
定理:比较-加法模型下,带非负实数权的有向图,存在确定性算法在 O(m log^{2/3} n) 时间内求出单源最短路。
稀疏图(m = Θ(n))上,Dijkstra 是 O(n log n),这里是 O(n log^{2/3} n)。因为 2023 年那篇无向图结果是随机化的,这篇也是无向图上第一个打破 O(m+n log n) 的确定性算法。
时间分析的骨架:递归树每一层,FindPivots 总时间 O(n k),共 O(log n / t) 层,乘起来 O(n k log n / t) = O(n log^{2/3} n)。堆结构上,pivot 插入合计 O(n t / k) 再乘层数仍是 O(n log^{2/3} n);每条边在整棵递归树里只会触发一次直接 Insert,合计 O(m(t + log k)) = O(m log^{2/3} n)。常数度变换之后 n 和 m 同阶,总时间就是 O(m log^{2/3} n)。
对照要分模型。整数权、word RAM 下,无向图 Thorup 已经线性,有向图 O(m + n log log min{n, C}),C 是最大边权。负权是另一条线:负整数近线性,负实数目前是次立方。这些都不能拿来直接比这篇的实数非负、比较-加法设定。
稀疏有向图、实数非负权、只要距离,Dijkstra 不是最优的。这句话 1959 年以来第一次有确定性算法撑着。
同时要看清它没推翻的那句:如果要按距离输出顶点序,Dijkstra 仍然最优。这篇赢在「不算全序」。工程上,斐波那契堆 Dijkstra 该用还是该用。BMSSP 递归、pivot、块状链表,常数和实现复杂度都不是给生产图库准备的,论文也没声称可实现性。
对做算法的人,可迁移的是前沿缩减:Bellman-Ford 几步把短依赖解掉,剩下的工作集中到少量大子树的根上,再分治。瓶颈路那一套层次和枢轴想法,在 SSSP 上第一次把有向图的排序壁垒凿开。
只处理非负权。负权、整数 RAM、近似算法,都不在这篇的模型里。
输出不含距离序。需要序的场景,Haeupler 等人的下界仍然卡死 Dijkstra。
常数度变换把顶点数扩到 O(m),分析里 n 其实是变换后的规模。log^{2/3} 这个指数从 k、t 的平衡里来,有没有更快的确定性指数,论文没给匹配下界。也没有实现,O 记号里的常数、递归开销、块状链表的工程表现全部未知。
比较-加法模型禁止对边权做位运算一类的操作,不能直接套 Thorup 那种 RAM 堆。假设所有路径长度唯一是靠字典序打破的,证明不依赖「现实中没有等长路径」,但实现时这个比较器必须带着走。