一句话总结

作者提出了一种确定性 $O(m \log^{2/3} n)$O(mlog2/3n) 时间算法，用于有向图上的单源最短路径（SSSP）问题，其边权为非负实数，打破了 Dijkstra 算法在稀疏图上长期存在的 $O(m + n \log n)$O(m+nlogn) 时间界，证明了在比较-加法模型中 Dijkstra 算法并非最优。

主要贡献

• 本文首次提出一种确定性算法，打破了有向图中单源最短路径（SSSP）问题在实数非负边权下 Dijkstra 算法长期存在的 $O(m + n \log n)$O(m+nlogn) 时间界，证明了 Dijkstra 方法在比较-加法模型中并非最优。

• 关键技术洞察在于一种递归的分治框架，将 Dijkstra 的前沿探索与 Bellman-Ford 风格的松弛相结合，从而实现一种新颖的前沿缩减技术，将需要排序的活跃顶点数量限制在 $O(|\widetilde{U}| / \log^{\Omega(1)} n)$O(∣U∣/logΩ(1)n)，从而绕过了 $\Omega(n \log n)$Ω(nlogn) 的排序瓶颈。

• 所得算法在稀疏图上运行时间为 $O(m \log^{2/3} n)$O(mlog2/3n)，标志着首次在有向图上实现对 Dijkstra 算法时间界的确定性改进，并扩展了可绕过基于比较的排序下界的一类图问题。

引言

作者解决了在有向图中以快于 $O(n \log n)$O(nlogn) 排序瓶颈的速度求解单源最短路径（SSSP）这一长期挑战，该瓶颈自然出现在边权为实数的比较-加法模型中。尽管先前工作已通过先进数据结构和随机化技术在无向图中打破了这一瓶颈，但有向图中尚无类似改进，Dijkstra 算法仍为标准方法，时间复杂度为 $O(m + n \log n)$O(m+nlogn)。现有方法的关键限制在于其依赖于按距离对顶点排序，这本质上需要排序操作，从而导致 $n \log n$nlogn 的开销。作者的主要贡献是一种突破性随机算法，打破了有向 SSSP 的排序瓶颈，实现了 $O(m \sqrt{\log n \log \log n})$O(mlognloglogn​) 的运行时间，从而证明了在有向图中 $n \log n$nlogn 的瓶颈并非根本性障碍。该结果推进了对 SSSP 的理论理解，并为比较-加法模型中的高效图算法开辟了新路径。

方法

作者提出了一种用于有向图上单源最短路径（SSSP）的确定性算法，边权为非负实数，达到 $O(m \log^{2/3} n)$O(mlog2/3n) 的时间复杂度，打破了 Dijkstra 算法在稀疏图上的长期 $O(m + n \log n)$O(m+nlogn) 界限。该方法的核心在于一种分治框架，通过基于距离界限递归划分图，避免了在每一步中对所有顶点进行完整排序。算法在常数度图上运行，其中每个顶点的入度和出度均有界，这是通过标准变换实现的，该变换在保持最短路径的同时确保了常数度性质。

主要计算引擎是有界多源最短路径（BMSSP）子程序，其设计目标是计算从一组源点 $S$S 到所有在给定距离界限 $B$B 内的顶点的最短路径。关键思想是维护一个动态前沿，即尚未完全处理但其最短路径必须经过当前已完全处理的 $S$S 中顶点的顶点集合。该算法通过递归缩小此前沿，避免了 Dijkstra 优先队列中固有的 $O(n \log n)$O(nlogn) 排序瓶颈。这一过程通过一个称为 FINDPIVOTS 的过程实现，该过程从 $S$S 中识别出一个更小的“枢纽”集合，足以引导递归计算。具体而言，FINDPIVOTS 对 $S$S 中的顶点执行 $k$k 轮边松弛，其中 $k = \lfloor \log^{1/3} n \rfloor$k=⌊log1/3n⌋。经过这些松弛后，任何其从源点出发的最短路径中包含至多 $k$k 个前沿顶点的顶点 $v$v 必然已完全处理。剩余的顶点，其最短路径需要通过前沿超过 $k$k 步，必须根植于一个大小至少为 $k$k 的最短路径树，且该树的根来自 $S$S 中的某个顶点。这些大树的根即为枢纽，其数量被限制在 $|U|/k$∣U∣/k，其中 $U$U 是关注的顶点集合。

[[IMG:|Framework diagram]]

BMSSP 算法本身是一个具有 $l$l 层的递归过程，$l$l 是与递归深度相关的参数。在每一层 $l$l，算法首先调用 FINDPIVOTS 以获得一组枢纽 $P$P 和一组顶点 $W$W，这些顶点要么已完全处理，要么依赖于枢纽。然后初始化一个数据结构 $\mathcal{D}$D，该结构是一个基于块的链表，用于高效管理键值对（顶点，距离），并支持插入、批量前置和提取最小元素等操作。该数据结构以枢纽 $P$P 作为键，关联其当前距离估计值进行初始化。随后，算法迭代地从 $\mathcal{D}$D 中提取 $M = 2^{(l-1)t}$M=2(l−1)t 个距离最小的顶点，其中 $t = \lfloor \log^{2/3} n \rfloor$t=⌊log2/3n⌋，并对每个这样的子集递归调用 BMSSP。在处理完递归调用后，算法松弛所有新完成顶点 $U_i$Ui​ 的出边，并根据其新的距离估计值将邻居插入 $\mathcal{D}$D。一个关键优化是使用批量前置，以高效地重新插入那些先前已处理但如今距离估计值可能改进的顶点。当已处理顶点总数 $|U|$∣U∣ 超过 $k2^{lt}$k2lt 时，递归终止，表示部分执行；当 $\mathcal{D}$D 变为空时，表示成功执行。

[[IMG:|Data structure diagram]]

该算法的正确性通过证明在每次递归调用中，距离小于 $B$B 的未完成顶点集合包含在当前源点集 $S$S 的最短路径树的并集中得以建立。数据结构 $\mathcal{D}$D 确保顶点按距离估计值递增顺序处理，且递归调用的设计覆盖了相关距离范围内的所有顶点。时间复杂度分析利用了每层递归中处理的顶点数量受限，且由于前沿缩减，每个顶点的处理工作量减少了 $\log^{1/3} n$log1/3n 倍。总运行时间主要由 FINDPIVOTS 过程和数据结构 $\mathcal{D}$D 上的操作成本决定，当参数 $k$k 和 $t$t 设置适当时，这些成本之和为 $O(m \log^{2/3} n)$O(mlog2/3n)。