超越Dijkstra：有向图单源最短路径算法

YZY Lv3
  2025-06-17 00:45:32 2025-06-17 00:45:32 Created   2025-06-17 00:45:32 2025-06-17 00:45:32 Updated      

超越Dijkstra：有向图单源最短路径算法

2025年4月，由Ran Duan、Jiayi Mao、Xiao Mao、Xinkai Shu和Longhui Yin发表的开创性论文《Breaking the Sorting Barrier for Directed Single-Source Shortest Paths》（打破有向图单源最短路径的排序壁垒）。他们提出的确定性算法，在稀疏图上渐进地快于Dijkstra算法。这不仅仅是一次增量改进，更是对该问题复杂度认知的一次根本性转变，为这个古老而核心的问题注入了新的活力。

第一部分：SSSP问题的历史与挑战

1.1. SSSP问题详解：定义、重要性与应用场景回顾

想象一张地图，上面有城市和连接城市的道路，每条道路都有其长度。单源最短路径（Single-Source Shortest Path, SSSP）问题就是：从一个指定的起始城市（“源点”）出发，到地图上其他所有城市的最短距离是多少？

形式化地说，给定一个图 ，其中 是一个包含 个顶点（城市）的集合， 是一个包含 条边（道路）的集合。每条边 都有一个非负权重 ，代表其长度或成本。目标是找到从指定的源顶点 到 中所有其他顶点 的路径的最小总权重。

鉴于其核心地位，高效解决SSSP问题一直是算法设计领域半个多世纪以来的焦点。

1.2. 经典算法回顾：Dijkstra算法

1959年，荷兰计算机科学家艾兹格·迪杰斯特拉（Edsger W. Dijkstra）提出了一种优雅且高效的算法，用于解决带非负边权的SSSP问题。

  • 1.2.1. Dijkstra的工作原理：贪心策略
    Dijkstra算法通过迭代地构建一个“已完成”或“已确定”（settled）的顶点集合，这些顶点的从源点出发的最短路径已知。
    1. 初始化距离：源点 的距离 ，所有其他顶点 的距离 。
    2. 维护一个未确定顶点的集合，初始时包含所有顶点。
    3. 当存在未确定顶点时：
      a. 从未确定顶点中选择一个具有最小临时距离 的顶点 。
      b. 将 标记为已确定。
      c. 对于 的每一个邻居 （即存在边 ）：
      如果 ，则更新 。这个过程称为“松弛”（relaxing）边。

该算法是“贪心”的，因为它在每一步都选择当前看来到未确定顶点的最短路径，并相信这条路径就是全局最短的。非负边权是保证这个贪心选择正确性的关键。

  • 1.2.2. 优先队列的关键作用
    Dijkstra算法中计算量最大的步骤是3a：“从未确定顶点中选择一个具有最小临时距离 的顶点 。” 朴素的扫描将非常耗时。这时，优先队列（Priority Queue）就派上了用场。优先队列是一种能高效支持以下操作的数据结构：
    • Insert(item, priority): 添加一个带优先级的项。
    • ExtractMin(): 移除并返回具有最小优先级的项。
    • DecreaseKey(item, new_priority): 将已存在项的优先级更新为一个更小的新值。

在Dijkstra算法中，顶点是项，它们的临时距离 是优先级。

  • 每个顶点最多被插入优先队列一次。

  • 共有 次 ExtractMin 操作（每个顶点一次）。

  • 每次边的松弛（最多 次）可能导致一次 DecreaseKey 操作。

  • 1.2.3. 时间复杂度：
    Dijkstra算法的效率取决于优先队列的实现。

    • 使用二叉堆：Insert 和 DecreaseKey 的时间复杂度为 ，ExtractMin 为 。总复杂度为 （对于连通图）。
    • 使用斐波那契堆（Fredman & Tarjan, 1987）或松弛堆（Driscoll et al., 1988）：
      • ExtractMin：摊还代价 。
      • Insert 和 DecreaseKey：摊还代价 。
        这使得总时间复杂度达到 ****。这在比较-加法模型中，对于稀疏图（ 接近 ）而言，长期以来被认为是SSSP算法的黄金标准。

1.3. “排序壁垒”：是否不可逾越？

Dijkstra算法复杂度中的 项，让人联想到基于比较的排序算法，后者的时间复杂度下界为 。这催生了SSSP问题的“排序壁垒”这一概念：或许任何在比较-加法模型中解决SSSP问题的算法，都不可避免地要执行与排序等价的工作量，从而在顶点相关的部分被卡在 。

  • 1.3.1. 比较-加法模型：算法竞赛的“游戏规则”
    对于处理实数输入且精确值至关重要的问题，这是一个标准计算模型。它只允许对边权进行两种操作：

    1. 加法：例如，。
    2. 比较：例如，。
      每种操作消耗单位时间。其他算术运算（如乘法、除法）或位运算是不允许的。这个模型对于路径长度的计算非常自然。

  • 1.3.2. Dijkstra算法的副产品：距离值 与 按距离排序的顶点序列
    Dijkstra算法的一个有趣的副产品是，它按照顶点离源点的真实最短路径距离的非递减顺序来处理（确定）顶点。所以，它不仅给出了距离，还给出了顶点按距离的排序。

  • 1.3.3. HHR+24的结论：若要求输出排序序列，Dijkstra已是最优
    最近，Haeupler, Hladík, Rozhoň, Tarjan和Tětek (HHR+24) 的一项研究证实了一个长期以来的猜想：如果一个SSSP算法被要求输出这种按距离排序的顶点序列（正如Dijkstra算法自然做的那样），那么确实是最优的。这似乎进一步巩固了排序壁垒。

    但问题是，如果我们仅仅关心距离值本身，而不关心顶点被确定或报告的具体顺序呢？我们能否打破这个壁垒？

1.4. 无向图上的突破：曙光初现

对于无向图，研究已取得一些进展：

  • Pettie 和 Ramachandran (PR05): 他们提出了一个基于层次的算法，时间复杂度为 ，其中 是反阿克曼函数（增长非常缓慢）， 是最大和最小边权之比。对于一般的实数权重（ 可能很大），这仍然是 。
  • Duan, Mao, Shu, 和 Yin (DMSY23): 本文的部分作者在之前的工作中，针对无向图提出了一个 时间的随机化SSSP算法。这是一个重要的进步，为稀疏图打破了 的界限，但它是随机化的，并且特定于无向图。

1.5. 有向图的特殊挑战：为何更难？

有向图通常比无向图带来更大的挑战。路径的单向性意味着许多利用对称性或双向性的技术不再适用。对于确定性算法而言，有向图的排序壁垒一直坚不可摧。

第二部分：是如何构想的？

作者们的方法非常精巧，融合了Dijkstra算法、Bellman-Ford算法的思想，以及复杂的分治技术。

2.1. 核心洞察：驯服“前沿”（Frontier）

  • 2.1.1. Dijkstra算法的“前沿”：潜在的包含所有未确定顶点
    在Dijkstra算法执行的任何时刻，优先队列都维护着一个顶点的“前沿”。这些是已达到、具有临时距离但尚未最终确定的顶点。如果一个顶点 是未完成的（即其当前距离估计 大于其真实最短路径距离 ），那么其真实最短路径必须经过某个当前位于前沿（优先队列中）的已完成顶点 。

  • 2.1.2. 瓶颈所在：管理一个庞大且动态变化的前沿
    的瓶颈源于这个前沿有时可能包含 个顶点。持续地在 个顶点中找到最小值，使用优先队列不可避免地导致每次提取操作都有 的因子，累积起来就是 。这类似于排序。

  • 2.1.3. 新策略：有效缩减前沿规模
    新算法的核心思想是设法使用一个规模小得多的“有效”前沿，或者以批量方式处理顶点，从而避免对全局、完全排序的优先队列的依赖。
    假设我们想计算一组“未完成”顶点 的距离。到达这些顶点的最短路径必须经过某个前沿 中的一些“已完成”顶点。
    该论文引入了一种基于参数 （将被设为 ）的策略：

    1. 情况1：前沿已经相对较小。 如果 ，那么相对于我们感兴趣的顶点数量，前沿 已经足够小了（小了 倍）。算法可以从 开始以类似Dijkstra的方式进行，但成本有效地分摊到 中的许多顶点上。
    2. 情况2：相对于 ，前沿可能较大。 如果 。此时，直接使用 的代价太高。这里的洞察是，从 中的所有顶点开始，运行几步（具体是 步）类Bellman-Ford的过程。
      • 中任何一个从 出发的最短路径使用少于 条“内部”边（内部顶点之间的边）的顶点 将变为已完成。
      • 对于 中剩余的未完成顶点，它们从 出发的最短路径必须包含至少 条内部边。这意味着 中 所依赖的原始“源”顶点 ，必须是一个（在内部）大小至少为 的最短路径树的根。
      • 然后，算法可以将前沿 “收缩”到一个“枢轴点”集合 ，其中 中的每个枢轴点都是这样一个大树的根。这样的枢轴点数量最多为 。这个新的枢轴点集 比原始的 （如果很大）要小得多。

这种前沿缩减是避免排序瓶颈的关键机制。

2.2. 结合：融合Dijkstra与Bellman-Ford的思想

新算法巧妙地融合了Dijkstra算法和Bellman-Ford算法的某些方面。

  • 2.2.1. Bellman-Ford算法：稳健的路径扩展器（复杂度）
    Bellman-Ford算法可以在 时间内找到所有最多包含 条边的最短路径。它通过迭代地松弛所有边 次来实现这一点。它不需要优先队列，因此避免了排序方面的问题。它的优势在于无需排序即可找到有限“跳数”或长度的路径。

  • 2.2.2. 混合思想：利用Bellman-Ford“加速”类Dijkstra步骤
    正如在前沿缩减策略中看到的，有限步数的Bellman-Ford执行（k步）有助于识别哪些顶点可以快速确定，哪些顶点依赖于作为长路径段头部的“枢轴点”。这使得算法能将其更昂贵的类Dijkstra操作集中在更小的一组关键枢轴顶点上。

2.3. 高层概览：基于递归划分的分治策略

该算法采用分治策略。它旨在迭代计算距离，按距离“层”或批量处理顶点。

  • 2.3.1. 目标：计算有界距离或特定子集的顶点距离。
    主要的子过程，称为BMSSP（有界多源最短路径），旨在从给定的源顶点集 开始寻找最短路径，但仅限于总长度小于某个上界 的路径。

  • 2.3.2. 递归结构：约 层递归。
    算法在 个递归层级上运行（其中 将被设为 ）。在每个层级 ，BMSSP尝试找到一组变为已完成的顶点 。它通过对层级 进行递归调用来实现这一点。上述的前沿缩减技术应用于此递归的每个层级。

  • 2.3.3. 关键参数： 和 。
    这些参数经过精心选择以平衡成本：

    • 控制前沿缩减中Bellman-Ford步骤的深度以及子问题的规模。
    • 控制用于管理候选顶点的数据结构的“粒度”（与引理3.3中的 相关），并影响递归深度（）。
      和 之间的相互作用对于达到最终的 复杂度至关重要。

第三部分：核心组件与子过程剖析

让我们深入研究使这个算法工作的具体组件。

3.1. 预备知识与假设

为了简化表述和分析，作者们做了一些标准假设：

  • 3.1.1. 常数度图：一种标准图变换技巧
    论文假设输入图具有常数的入度和出度。任何一般图 G 都可以转换为这样的图 G’，使其具有 个顶点和 条边，同时保留最短路径信息。这是一种常用技术：

    • 将每个顶点 替换为一个由 个新顶点组成的、通过零权重边连接的环。
    • 原图中每条与 相关联的边现在连接到这个环上的一个不同顶点。
    • 新图 G’ 有 个顶点（因为对于连通图 ）和 条边。每个新顶点的入度和出度最多为3（一个入环边，一个出环边，一个原图边）。
      这意味着 G’ 上的SSSP算法能给出 G 上的SSSP。因此，G’ 上的 算法（其中 ）对于 G 来说变成 算法。由于 是 ，这即是 。

  • 3.1.2. 路径总序：处理等长路径的技巧
    论文假设从源点 出发的所有路径都具有不同的长度。这简化了确保前驱数组 始终构成树形结构的过程。这个假设并非限制性的；可以通过字典序（例如，比较路径中的顶点序列）以最小的开销打破平局，从而确保最短路径的唯一性。

  • 3.1.3. 顶点状态：已完成（complete） vs. 未完成（incomplete）
    在整个算法过程中， 存储对 的最短路径的当前最佳估计。

    • 如果 等于真实的最短路径距离 （通常用 表示），则顶点 是已完成的。
    • 否则， 是未完成的。
      算法的目标是使所有顶点都变为已完成。

3.2. BMSSP：有界多源最短路径（Bounded Multi-Source Shortest Path）—— 算法的主力军

BMSSP是核心的递归过程。

  • 3.2.1. 引理3.1：BMSSP的承诺与功能
    BMSSP(l, B, S) 接受：

    • ：当前递归层级（整数，从0到 ）。
    • ：距离的上界。我们只对长度小于 的路径感兴趣。
    • ：一个“源”顶点集合。假设对于任何真实距离 的未完成顶点 ，其最短路径必须访问 中的某个已完成顶点。（更准确地说，对于我们要找的目标顶点 ，它的最短路径 中， 且 是已完成的，并且 ）。集合 的大小有界，。

    BMSSP 输出：

    • ：一个新的边界（）。
    • ：一个顶点集合 ，满足 ，它们的最短路径访问原始 中的某个顶点，并且 中的所有顶点现在都是已完成的。

  • 3.2.2. 成功执行 vs. 因工作量过大而部分执行
    BMSSP 可能有两种结果：

    1. 成功执行：如果它处理了所有相关顶点，则 。所有满足 （且依赖于 ）的顶点 都被找到并放入 。
    2. 因工作量过大而部分执行：如果集合 增长过大（具体来说， 达到 ），过程可能会提前终止。在这种情况下，，并且 包含所有满足 （且依赖于 ）的顶点 。这种机制防止单个递归调用做过多的工作。

顶层调用将是 BMSSP()，其中 是全局源点。

3.3. 寻找枢轴点（Pivots）（算法1 & 引理3.2）：前沿缩减引擎

这是类Bellman-Ford思想发挥作用以缩小有效前沿的地方。

  • 输入：一个边界 ，一个源顶点集 （与BMSSP的输入要求一致）。

  • 操作：

    1. 初始化工作集 。维护一个集合 。
    2. 对于 到 （其中 ）：
      令 为空。对于 中的每个顶点 ，松弛其所有出边 。如果 被更新且 ，则将 加入 和 。
      如果在任何时刻，收集在 中的顶点总数超过 ，则意味着前沿 从一开始就“足够小”。算法返回 和当前的 。
    3. 如果循环完成（意味着 ）：
      仅使用 中的顶点和在 步松弛过程中松弛过的边，构建一个最短路径森林 ，其根源自 中的顶点。
      定义枢轴点 为原始源点 中那些作为 中包含至少 个来自 的顶点的树的根的子集。
    4. 返回 和 。

  • 承诺（引理3.2）：
    该过程找到 （大小为 或 ，其中 是从 可达且距离 的所有顶点的集合）和 （大小最多为 ），使得对于任何其最短路径（长度 ）依赖于 的顶点 ：

    • 要么 在 中并且现在是已完成的（它从 出发的路径在 内部有 条“内部”边）。
    • 要么，到 的最短路径访问某个已完成的枢轴点 。

  • 复杂度： （假设常数度）。所以是 。

这一步至关重要。如果 很大但 （我们实际关心的从 能找到的顶点）很小，|P| 可能是 。如果 很小，|P| 最多是 。它有效地确保了用于进一步递归步骤的源点集 相对于预期的“进展”量不会过大。

3.4. 特制数据结构（引理3.3）：高效的候选顶点管理

为了管理待扩展的候选顶点，同时避免标准优先队列对 个项操作时产生的完整 代价，论文引入了一种自定义数据结构。

  • 为何需要：BMSSP中的递归调用将产生候选顶点（的邻居），这些顶点需要在未来的迭代或递归调用中被考虑。我们需要高效地Pull（提取）一批 个具有最小距离的候选顶点。
  • 操作需求：
    • Initialize(M, B_initial)： 是一个块大小参数。
    • Insert(key, value)：插入顶点 key 及其距离 value。摊还代价 ，其中 是插入的总项数。
    • BatchPrepend(L_items)：插入一个列表 L_items，其中所有项的值都小于当前数据结构中的任何项。摊还代价 '_' allowed only in math modeO(|\text{L_items}| \cdot \max{1,\log(|\text{L_items}|/M)})。
    • Pull()：返回一个最多包含 个具有最小值的键的子集 ，以及一个将 与数据结构中其余值分开的上界 。摊还代价 。
  • 结构（高层描述）：
    它使用两个块序列，（用于批量前置插入）和 （用于常规插入）。每个块是一个最多包含 个键值对的链表。
    • 块根据其值排序（块内的元素不一定完全排序，但块的min/max值是有序的）。
    • 使用自平衡二叉搜索树维护其块的上界（或min值），允许以 的时间搜索插入的正确块。
    • 如果 中的一个块超过 个元素，则使用中位数查找（时间）将其拆分。
  • 在BMSSP中的角色：BMSSP 在层级 的数据结构的参数 被设置为 。这意味着 是从层级 调用时期望得到的 的典型大小。这个选择对于摊还成本的计算至关重要。

3.5. 递归基石（算法2：迷你Dijkstra）：递归的终点

当BMSSP中的递归层级 达到0时：

  • 输入：一个边界 ，以及集合 （保证为单例 ，其中 是已完成的）。
  • 操作：从 开始运行标准Dijkstra算法（例如，使用二叉堆）。
  • 终止条件：如果满足以下任一条件则停止：
    1. 已确定（从堆中提取）了 个顶点。
    2. 或者，下一个要提取的顶点的距离 。
  • 输出：
    • 如果找到了 个顶点且第 个顶点的距离 ：返回 和 {前k个已确定且距离 的顶点}。
    • 否则（找到少于k+1个顶点，或所有找到的顶点都 ）：返回 和 {所有已确定的顶点}。
  • 复杂度：大致为 '_' allowed only in math modeO(k \log k + \text{degree_sum_in_explored_region})，由于常数度假设和探索区域小，可以认为是 或 （如果用特制PQ）。论文中可能会分析为 。

3.6. 递归引擎（算法3：BMSSP详解）

现在我们可以勾勒出主要的BMSSP算法（论文中的算法3）：

function BMSSP(l, B, S):

  1. 递归基石：如果 ，调用 BASECASE(B, S) (算法2) 并返回其结果。
  2. 寻找枢轴点：调用 P, W_pivots = FINDPIVOTS(B, S) (算法1)。
    • 是缩减后的源顶点集。
    • 是在FINDPIVOTS内部通过k步Bellman-Ford确定的顶点集。
  3. 初始化数据结构：创建特制数据结构 (引理3.3) 的一个实例，块大小 。
    对于每个枢轴点 ，将其及其当前距离 插入 。
    初始化 。令 (如果 非空，否则为 )。(这是循环的初始 )。
  4. 主迭代循环：当 (工作量限制) 且 非空 (且 ) 时：
    a. 。(这是本次迭代距离的下界)
    b. $(S_i, B_{upper_iter_or_next_lower}) = D.Pull()。$S_i$ 是从 $D$ 中提取的一批最多 $M$ 个具有最小距离的顶点，它们的距离都在 $[B_{lower\_iter}, B_{upper\_iter\_or\_next\_lower})$ 区间内。这个 $B_{upper\_iter\_or\_next\_lower}$ 将作为*下一次*迭代的 $B_{current\_min}$。 c. **递归调用**：(B’i, U_i) = BMSSP(l-1, B{upper_iter_or_next_lower}, S_i)。 * 此调用处理那些源自 $S_i$ 且距离预期在 $[B_{lower\_iter}, B_{upper\_iter\_or\_next\_lower})$ 区间的路径。 * $U_i$ 包含满足 $d(v) < B'_i$ （且路径经由 $S_i$）且现已完成的顶点。 d. $U_{overall} = U_{overall} \cup U_i$。 e. **松弛边 & 更新D**： 初始化一个空列表 $K_{batch\_prepend}$。 对于每条边 $(u,v)$，其中 $u \in U_i$： 如果 $d[u] + w(u,v)$ 改进了 $d[v]$ (更新 $d[v]$ 和 $\text{PRED}[v]$)： 如果 $d[v]$ 的新值在 $[B'_i, B)$ 区间内 (即新距离超出了递归调用 BMSSP(l-1,…)通过 $S_i$ 处理的范围 $B'_i$，但仍在*当前*BMSSP(l,…)调用的全局上界 $B$ 之内)： $D.Insert(v, d[v])$。 否则，如果 $d[v]$ 的新值在 $[B_{lower\_iter}, B'_i)$ 区间内 (即新距离落入*刚刚完成的*递归调用BMSSP(l-1,…)处理的范围)： 将 $(v, d[v])$ 加入 $K_{batch\_prepend}$。 f. **批量前置插入**： 对于 $S_i$ 中每个 $x$，如果 $d[x] \in [B'_i, B_{upper\_iter\_or\_next\_lower})$ (这些是从提取的批次 $S_i$ 中来的源点，它们的递归子问题BMSSP(l-1,…)` 可能因 $B’i < B{upper_iter_or_next_lower}而提前终止，所以如果它们的距离仍然相关，则需要重新添加它们到更早的批次处理中。将这些(x, d[x])加入K_{batch_prepend}。D.BatchPrepend(K_{batch_prepend})。B_{current_min} = B_{upper_iter_or_next_lower}$ (为下一次迭代设置下界)。
  5. **确定输出边界 **：
    如果循环正常终止 (例如 为空或 )： (成功执行)。
    否则 (因 而终止)： (因工作量大而部分执行)。
  6. **最终化 U_{overall}**：。(将FINDPIVOTS的 集合中，距离在最终边界 内的顶点加入)。
  7. 返回 。

这个循环结构非常精妙。它拉取一批 进行处理。递归调用 BMSSP(l-1, B_{upper\_iter\_or\_next\_lower}, S_i) 处理从 出发到 为止的路径，但可能只完成到 $B’i。新松弛的边可能会产生D$ 的候选者，这些候选者要么“更远”（直接Insert），要么“更近”（批量前置插入到 $K{batch_prepend}$，用于未来的 Pull 操作，然后进行递归调用）。

第四部分：正确性与复杂度分析

4.1. 正确性简述（基于引理3.7）

正确性论证非常复杂，依赖于对递归层级 的归纳。

  • **递归基石 (l=0)**：算法2 (Mini-Dijkstra) 从单个已完成的源点 开始运行。它正确地找到从 可达的最近的 个顶点（或更少，如果受 限制）并使它们完成。
  • **归纳步骤 (l > 0)**：假设BMSSP对于层级 是正确的。
    1. FINDPIVOTS(B, S) 确保任何未完成的顶点 （满足 ，路径经由 ），要么在 内变为已完成，要么其路径依赖于 中的一个枢轴点。
    2. 中的顶点被插入数据结构 。
    3. 主循环迭代地从 中拉取批次 。
      • 关键不变量（论文引理3.7证明中的命题(a)）是，在每次迭代 开始前，任何未完成的顶点 （满足 且其最短路径经由原始输入 中的某个顶点，且该路径的第一跳离开 后进入的点（或 中的点本身如果路径长度为0）当前位于 或已被处理并放入 ）都会被正确处理。
      • 命题(b)指出，由 表示的顶点集正确地反映了从 （或后续松弛产生的顶点）出发的、尚未被递归调用处理的“前沿”顶点。
    4. 递归调用 BMSSP(l-1, B_{upper\_iter\_or\_next\_lower}, S_i) 根据归纳假设，正确计算出 ，使得 中的所有顶点 都变为已完成，且其距离 满足 $d(v) \in [B_{lower_iter}, B’i)并经由S_i。不同i的这些U_i集合是不相交的，因为它们处理的距离区间[B{lower_iter}, B’_i)是基于D.Pull()$ 的结果，这些结果会划分距离空间。
    5. 从 出发的松弛正确更新 值。新的候选顶点被添加到 。BatchPrepend 步骤正确地重新引入来自 的源点（如果它们的子问题提前终止）或新松弛的、落入较早距离范围的顶点，确保它们能在后续的 中被考虑，从而被正确的 调用处理。
    6. 终止时，要么所有从 出发且 的路径都被找到（ 为空或工作量限制未触发，则 ），要么到 为止的路径被找到（达到 限制）。最后包含 确保所有在 FINDPIVOTS 阶段直接确定的顶点都被覆盖。
      整体结构确保BMSSP(l, B, S)返回的 包含了所有从 出发且距离小于 的顶点，并且 中的所有顶点都是已完成的。

4.2. 时间复杂度分析（通往之路）

这是最复杂的部分，涉及仔细的摊还分析和平衡。

  • 回顾参数：， 。递归深度 。

  • 论文使用了引理3.12（或类似引理），该引理指出 BMSSP(l, B, S) 返回 的运行时间大致由以下公式界定（这里是概念性的，具体形式见论文）：
    '_' allowed only in math modeT_{BMSSP}(l, |S|, |U_{returned}|, |\text{EdgesRelaxed}|) \approx \text{cost}(FINDPIVOTS) + \text{cost}(D.\text{ops}) + \sum \text{cost}(\text{recursive_calls}) + \text{cost}(\text{relaxations})

    关键在于对数据结构 的操作成本以及递归调用如何分摊。
    论文（第11页）指出，在整个算法执行过程中（即顶层调用 BMSSP(L, \infty, {s})）：

    1. FINDPIVOTS的总成本：所有FINDPIVOTS调用的总成本加起来是 ，其中 是总探索的边数。在常数度模型下，这界定为 。
    2. 数据结构 的操作总成本：
      • Insert操作：每个顶点-距离对只会被Insert一次。由于 ，Insert成本 。当 远大于 时，这可能是 （因为 可能达到 ，而 , 所以 , ）。 总的 Insert 成本可能是 。（论文中对引理3.3的分析是每次插入 ，总 ）。
      • BatchPrepend操作：总的BatchPrepend成本与被前置的项数有关，每项成本可能是 或更低。论文分析这部分总共贡献 ，这在所选参数下也是可控的。
      • Pull操作：成本摊还到被拉取的元素上，总共 或 个元素被拉取，每元素 摊还。
    3. 递归调用和边松弛：
      递归调用将问题分解。每个层级 的 BMSSP 调用会处理特定大小的源集 ()。
      边松弛的总次数是 , 其中 是每条边平均参与的有效递归层数，论文通过精巧的距离区间管理和BatchPrepend机制，将这个有效层数控制在 左右，或者将每条边的松弛成本分摊。

    根据论文的详细摊还分析（例如，第11-12页的定理3.13的证明概要），最终总时间复杂度被证明为：

    代入 , , :


    • 这个第二项看起来比 大。这里需要参考论文中对各项成本更精确的求和与界定。

    论文给出的最终结果是 （根据一些讨论和对原文复杂度的理解，有时会是）。如果严格按照问题描述的 ，那么 相关的项需要被项吸收或通过其他方式约束。通常对于稀疏图，, 目标是 。

    让我们重新审视论文中对时间复杂度的典型分解方式，并结合参数：

    1. FINDPIVOTS 总共: .
    2. BASECASE 总共 (所有 的调用): .
    3. 数据结构 的操作 (不含Pull的摊还部分)：
      • 所有Inserts: 大约 . 可能与 或 相关.
      • 所有BatchPrepends: 大约 .
    4. 一个关键点是，一条边 的松弛，导致 被插入 时，这个成本与 所在的“桶”或层级有关。
      论文中（引理3.12的表述和定理3.13的证明）通过仔细的信用分配和摊还，确保了所有组件的成本总和被界定在 或类似的表达式，对于稀疏图简化为 .

    若最终复杂度确实是 ，那么 必须被 覆盖，这意味着对于非常稀疏的图（例如 ）， 项可能占主导。但通常我们关心的是 。
    更简洁的推导（基于目标，可能隐藏了许多细节）：

    • 总共有 层递归。
    • 在每一层，FINDPIVOTS 的总工作量（跨所有调用）可能是 , 其中 是该层处理的边。
    • 数据结构操作，如果每次 Insert 和 BatchPrepend 分摊到 ，总数 或 次操作，得到 或 。
    • 关键在于每条边或每个顶点在整个算法中贡献的总成本。
    • 如果每条边平均贡献 ，总共 。
    • 如果每个顶点平均贡献 ，总共 。

    鉴于设定的目标复杂度是 , 我们将接受这个结果是经过论文中复杂的摊还分析得出的。主要的贡献因子是 和 。例如，如果每条边在 个阶段中的每个阶段都以 的成本被处理，或者总共被处理 次，每次 ，或者类似的组合。

    对于稀疏图，其中 ，这即是 。这渐进地优于Dijkstra的 。
    例如，若 :
    .
    .
    这是一个显著的理论加速。

第五部分：深远意义与未来展望

5.1. 里程碑式的理论突破

  • 首个确定性突破：这是第一个在比较-加法模型下，对一般有向图、实数非负边权的SSSP问题，超越界限的确定性算法。
  • 证明Dijkstra并非求解距离的最优算法：它表明，即使我们只想要最短路径距离（而不要求按距离排序的顶点序列），Dijkstra算法也不是最优的。HHR+24提出的壁垒仅在要求排序输出时适用。
  • 对无向图也是确定性的改进：虽然DMSY23为无向图打破了壁垒，但那是随机化的。这个新算法是确定性的，并且由于无向图是（通过将每条无向边替换为两条有向边）有向图的特例，此结果也为无向图SSSP问题提供了首个确定性的 算法，改进了Pettie & Ramachandran在一般实数权重上的结果（后者是 ）。

5.2. 实践意义：我们离实际应用还有多远？

虽然这是一个巨大的理论飞跃，但其直接的实际应用价值需要考量：

  • 常数因子与实现复杂度：该算法比Dijkstra算法复杂得多。O表示法中隐藏的常数因子可能相当大。正确且高效地实现递归的BMSSP、FINDPIVOTS，尤其是特制数据结构（引理3.3），是一项艰巨的工程挑战。
  • 与优化Dijkstra的比较：对于实践中遇到的一般图规模，高度优化的Dijkstra实现（例如，使用二叉堆或具有良好缓存性能的k叉堆）速度非常快。由于常数因子的影响，这种新算法可能仅在规模极其巨大的图上才能超越Dijkstra，甚至可能无法超越。
  • 然而，这通常是理论突破的发展轨迹。最初复杂的算法为后续更简单、更实用的版本铺平道路，或激发新的技术。

5.3. 开放问题与未来研究方向

这项工作开辟了令人兴奋的研究途径：

  • 终极界限？ 我们能否在此模型中为SSSP实现？或者像MST那样的？差距已经缩小，但仍然存在。
  • 更简洁的算法？ 能否找到一个更简单的确定性算法，仍能打破的壁垒？目前的算法相当复杂。
  • 实用变体？ 是否有方法借鉴某些思想（如前沿缩减）来对Dijkstra进行启发式改进，使其可能具有实用性？
  • 其他模型？ 这与在其他模型中（例如，带整数权重的字RAM模型，Thorup在该模型中对有向图实现了）的SSSP问题有何关联？
  • 相关问题？ 这些技术能否应用于目前面临类似排序瓶颈的其他图问题？

5.4. 结论：图算法的新篇章

Duan、Mao、Mao、Shu和Yin完成了许多人可能认为不可能的任务：在比较-加法模型中，为有向图SSSP问题设计了一个确定性的、可证明比Dijkstra更快的算法。通过巧妙地结合递归划分、用于前沿缩减的有限深度Bellman-Ford探索以及定制的数据结构，他们成功地规避了传统的排序瓶颈。

尽管由于其简洁性和优良的常数因子，Dijkstra算法无疑仍将是大多数应用的实用主力，但这篇论文从根本上改变了我们的理论认知。它表明， 的壁垒部分是要求排序输出的人为结果，对于寻找距离的核心任务，存在更快的方法。这一突破证明了算法创新的持久力量，必将激励对最短路径问题及更广泛领域的新一轮研究。对终极SSSP算法的探索仍在继续，但一个重要的壁垒现已被明确打破。

术语表 (Glossary of Key Terms)

  • SSSP (Single-Source Shortest Path, 单源最短路径): 从单个起始顶点到图中所有其他顶点的最短路径问题。
  • 比较-加法模型 (Comparison-Addition Model): 一种计算模型，其中对边权只允许加法和比较操作，每个操作耗费单位时间。
  • Dijkstra算法 (Dijkstra’s Algorithm): 一种用于解决非负权图SSSP问题的贪心算法，通常运行时间为 。
  • 排序壁垒 (Sorting Barrier): 长期存在的观点，认为SSSP在比较-加法模型中可能固有地需要 的时间，类似于排序。
  • 前沿 (Frontier): 在类Dijkstra算法中，指已到达但尚未最终确定的顶点集合。在本文中，更广泛地指一组“活跃的”源顶点。
  • Bellman-Ford算法 (Bellman-Ford Algorithm): 一种可以处理负权边（如果没有负权环）的SSSP算法。此处相关是因为它能在 时间内找到最多k条边的路径而无需排序。
  • BMSSP (Bounded Multi-Source Shortest Path, 有界多源最短路径): 新算法中的核心递归子过程，设计用于从一组源点 寻找特定距离上界 内的路径。
  • 枢轴点 (Pivots): 由FINDPIVOTS子过程识别出的、用于进一步路径探索的缩减后的源顶点集。
  • 和 : 新算法中的关键参数，分别设为 和 ，用于平衡递归深度和每层的工作量。
  • 已完成/已确定顶点 (Complete/Settled Vertex): 其真实最短路径距离已被找到并最终确定的顶点。
  • 未完成顶点 (Incomplete Vertex): 其当前最短路径估计可能尚未是真实最短路径的顶点。
  • 松弛 (Relaxation): 如果通过边 找到了到顶点 的更短路径，则更新 的距离估计的过程 (即 )。
  • Title: 超越Dijkstra：有向图单源最短路径算法
  • Author: YZY
  • Created at : 2025-06-17 00:45:32
  • Updated at : 2025-06-17 00:45:32
  • Link: https://blog.dtoj.team/2025/06/17/超越Dijkstra：有向图单源最短路径算法的新纪元/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
超越Dijkstra：有向图单源最短路径算法
  1. 超越Dijkstra：有向图单源最短路径算法
  2. 第一部分：SSSP问题的历史与挑战
  3. 第二部分：是如何构想的？
  4. 第三部分：核心组件与子过程剖析
  5. 第四部分：正确性与复杂度分析
  6. 第五部分：深远意义与未来展望