论文阅读：Breaking the Sorting Barrier for SSSP

STOC 2025 的这篇论文《Breaking the Sorting Barrier for Directed Single-Source Shortest Paths》将单源最短路径问题的时间复杂度做到了 $O(m\log^{\frac{2}{3}}n)$，在稀疏图上优于 Dijkstra 的 $O(m + n\log n)$。

1. 假设

论文首先做了两个假设：

• 图上每个点的入度和出度均为常数，比如 $2$。这样就有 $m=\Theta(n)$。这样的假设可以保证后续一个点向外松弛时时间复杂度不会炸（最多松弛两次）
• 图上每个点的最短路长度都是不同的。这样的假设可以保证每个点的最短路前驱最多只会有一个，最短路关系一定形成的是最短路树而不是 DAG。

在最后我们会解释这两个假设是不失一般性的。

2. 算法过程

算法有两个参数，$k$ 和 $t$，并且设 $k = \left \lfloor \log^{\frac{1}{3}}n \right \rfloor$，$t = \left \lfloor \log^{\frac{2}{3}}n \right \rfloor$。后续我们会看到，这样的两个参数可以得到最后 $O(m\log^{\frac{2}{3}}n)$ 的时间复杂度。

论文中为了叙述方便，还引入了如下符号：$d(x)$ 表示 $x$ 最终的最短路距离，$\hat{d}(x)$ 表示 $x$ 当前距离。

为了方便后面叙述，我们称一个节点 complete ，就表示这个节点的最短路已经找到了。一个 complete 的点即满足 $d(x) = \hat{d}(x)$。

算法的主体部分是 BMSSP 算法，BMSSP 又用到了两个部分：Finding Pivots 和一个神秘的数据结构。对于后者，我们在这里将其称之为分块优先队列。

2.1 BMSSP

BMSSP 算法是整篇论文的主体。BMSSP 算法接收三个参数 $l$，$S$ 和 $B$。

• $l$ 表示当前层数，BMSSP 的过程有点类似于分治，有一个递归过程，而在不断递归的时候，BMSSP 的层数会一直降低，直到 $l=0$，我们就说到达了一个 BaseCase。在 BaseCase 时，会走另一个算法，我们一会再说。
• $S$ 表示一个集合。
• $B$ 表示一个上界。

BMSSP 仅考虑最短路长度小于 $B$，且没有 complete 的点。我们将这种点称为目标节点。这些节点组成集合 $\widetilde{U}$。

同时 BMSSP 还对上述参数做了如下要求：

• $S$ 不能太大：$|S| \le 2^{lt}$。
• 你需要保证 $\widetilde{U}$ 中所有的点的最短路，都经过 $S$ 中某个已经 complete 的点（一个点的最短路肯定是由某个已经找到最短路的点推过来的）。这也就意味着 $S$ 中必须有至少一个 complete 的点（但不意味着 $S$ 中的点都是 complete 的，$S$ 里面混杂着 complete 和没 complete 的点）（同时后续算法会保证，$B$ 一定大于 $S$ 中最大的 $\hat{d}$ ，这也就意味着 $S$ 中没被 complete 的点的最短路一定是经过已经 complete 的点）。

当执行完一次 BMSSP 算法之后，会产生两种情况：

• 成功执行：BMSSP 会把 $\widetilde{U}$ 的点全部 complete，（由于第二个要求，这件事是肯定能办到的）
• 部分执行：BMSSP 为了控制时间复杂度，只 complete 掉 $\widetilde{U}$ 内的一部分点。

然后算法会返回一个集合 $U$ 和一个边界 $B'$。表示说所有最短路长度小于 $B'$，且没有 complete 的点，都已经被 complete 掉，且放入集合 $U$ 中了。

对于成功执行情况，就会有 $U=\widetilde{U}$，$B'=B$。对于部分执行情况，就会有 $U\subset \widetilde{U}$，$B'<B$。返回这两个值可以让调用方得知 BMSSP 完成的进度。

然后我们要求点 $x$ 的单源最短路的话，只需要令 $l=\left\lceil \frac{\log n}{t} \right\rceil$（为什么是这样后面会解释），$S=\left\{x\right\}$，$B=\infty$ ，跑 BMSSP 就可以了。

然后我们来看 BMSSP 是怎么做的：

既然我们已经在 BMSSP 中的第二个要求中说，我们的目标节点最短路一定是经过 $S$ 的，那么朴素的想法是从 $S$ 出发往外松弛。论文则提出，我们可以先搞一个 Finding Pivots 操作，先把 $S$ 的规模缩一下，缩成 $P$，然后再从 $P$ 往外松弛。同时 Finding Pivots 操作在缩小规模的时候还顺便 complete 掉一些点，这些点被放在 $W$ 中（但 $W$ 里面还混杂着一部分没有 complete 的点，需要后面再筛出来）。

朴素的 Dijkstra 会使用堆，把 $S$ 都放入堆中，然后每次把 $\hat{d}$ 最小的点拿出来往外松弛（$\hat{d}$ 最小的点一定是已经 complete 的，或者说有 $\hat{d} = d$）。堆的这个排序是 Dijkstra 时间复杂度的瓶颈，所以论文为了避开这点，选择使用一个分块的优先队列来维护 $\hat{d}$。分块的大小为 $M$。可以往这个分块优先队列里插入，或是批量插入（批量插入的时间复杂度会小一点，但同时需要满足批量插入的数据比分块优先队列中最小的数据还要小），或是取出前 $M$ 个最小的数据。

于是 BMSSP 就用分块优先队列，以类似朴素的 Dijkstra 的方法进行求解。首先把 $P$ 都放入这个分块优先队列中，然后每次循环，把分块优先队列中前 $M$ 小的点拉出来，记为 $S_i$（$S_i$ 内可能是无序的）。拉出来的时候数据结构还会返回一个上界 $B_i$，$B_i$ 为分块优先队列中剩余的最小的 $\hat{d}$（也意味着 $B_i$ 比 $S_i$ 中最大的 $\hat{d}$ 还大）。

由于 $S_i$ 内的点不是全部 complete 的，所以不能直接往外松弛。BMSSP 就会先拿着 $S_i$ 和 $B_i$ ，去调用 $l-1$ 层的 BMSSP。首先，由于 $|S_i|\le M = 2^{(l-1)t}$（当分块优先队列里的数据不足 $M$ 个的时候，$|S_i|< M$），所以满足下一层 BMSSP 的第一个要求。事实上，对于第二个要求也是成立的，即所有最短路长度小于 $B_i$ 的点的最短路事实上就是经过 $S_i$ 的（后面正确性部分会细说，这个对应正确性部分的 Pull Minimum 引理）。调用完之后就拿到了子 BMSSP 返回的 $U_i$ 和 $B_i'$。$U_i$ 是子 BMSSP complete 掉的点的集合，我们把他直接并入当前 BMSSP 的 $U$ 中。

现在 $U_i$ 已经是 complete 的了，于是从 $U_i$ 往外松弛。对于边 $(u,v)$，如果松弛成功的话，根据朴素的 Dijkstra，我们需要把 $v$ 放入堆中。我们这里也是一样，只不过我们需要对 $\hat{d}(v)$ 进行讨论：

• $\hat{d}(v)\ge B$，这个我们就不管了，因为当前 BMSSP 只负责最短路小于 $B$ 的部分。
• $B_i\le \hat{d}(v) < B$ ，我们把 $v$ 直接插入分块优先队列中。
• $B_i'\le \hat{d}(v) <B_i$，我们也把 $v$ 插入分块优先队列中。但是注意，我们之前说，分块优先队列中剩余数据的最小值是 $B_i$，这意味着 $\hat{d}(v)$ 比最小值还要小，可以使用批量插入来加速。
• $\hat{d}(v) < B_i'$ ，不可能，因为既然子 BMSSP 返回了 $B_i'$，就说明最短路距离小于 $B_i'$ 的点都被 complete 了。一个已经 complete 的点是不可能再被有效松弛的。

同时，由于子 BMSSP 部分执行的原因，可能 $S_i$ 有部分点他本身的 $\hat{d}$ 就大于了 $B_i'$，没派上用场，所以需要把这部分点也重新放回分块优先队列中。这部分点的 $\hat{d}$ 也是小于 $B_i$ 的，所以可以批量插入。需要批量插入的点都放入集合 $K$ 中，在最后统一批量插入。

每次循环开始还会检查当前已经 complete 的点数量，即集合 $U$ 的大小，是否超过了 $k2^{lt}$，超过的话就说明当前 BMSSP 的工作量有点大了，需要立刻终止。因此，为了保证最顶层的 BMSSP 一定是成功执行的，我们必须让顶层的 $l$ 满足 $k2^{lt}>n$。$l=\left\lceil \frac{\log n}{t} \right\rceil$ 是满足的，所以我们最顶层的 BMSSP 取了这个值。（这个值偏大，但是不影响时间复杂度）。

在 BMSSP 的最后，会把最后一次子 BMSSP 的返回值 $B_i'$ 作为返回值 $B'$。然后这里有一点：$W$ 集合中，满足 $\hat{d}$ 小于 $B'$ 的点就是先前 $W$ 中已经 complete 的点（为什么是这样会在后面将 Finding Pivots 的时候说）。把这些点都筛出来放入集合 $U$，就组成了当前 BMSSP 所有 complete 掉的点。

你可以这么直观地理解 BMSSP：我们的目标是把最短路距离位于 $[0, B)$ 的点全部 complete 掉。前 $i-1$ 次循环，子 BMSSP 把这个进度推进到了 $B_{i-1}'$。第 $i$ 次循环，我们希望子 BMSSP 把进度推进到 $B_i$，但是子 BMSSP 可能由于部分执行的原因，只把进度推到了 $B_i'$。当前 BMSSP 也可能由于工作量太大，强行终止，使得最后的进度也没到 $B$，只到了最后一次子 BMSSP 推进到的进度。

2.2 BaseCase

注意，上面 BMSSP 的分块优先队列 $D$ 保证了每次取出的 $S_i$ 的大小不超过 $M$。当 $l=1$ 时，$M=1$，所以再往 $l=0$ 这一层传的 $S_i$ 只有一个元素了。同时根据 BMSSP 的第二个要求，可以得知此时跑一个 Dijkstra 是没问题的：

在 BaseCase 中同样的需要满足 $|U|<k2^{lt}$，以及只关心最短路小于 $B$ 的点。

2.3 分块优先队列

然后我们先讲点数据结构。

对于分块优先队列的直观的感觉已经在上面说了，就是顾名思义，分块的优先队列，把数据一块一块地维护，块内的数据是乱序的，块间是有序的（也就是前一个块的最大值小于后一个块的最小值）。

更具体地说，这个数据结构维护了若干个 key-value，有两个给定的参数 $M$ 和 $B$，数据结构中最多会维护 $N$ 个 key-value。然后想要有如下的操作：

• Insert：插入一对 key-value，如果 key 已经存在于数据结构中，那么就更新它的 value。所有的 value 值不超过一个边界值 $B$。
• Batch Prepend：如果有若干个 key 的 value 值比数据结构中已有的最小 value 还要小，那么这堆 key 可以批量插入。
• Pull：从这个数据结构中取出 value 最小的 $M$ 个 key 并从数据结构中删除。如果已有的 key 不足 $M$ 个，则把所有的 key 都取出来。同时该操作还返回一个上界 $x$，表示数据结构中剩余的元素中的最小 value 的值（如果最后数据结构里不剩东西了，就把 $x$ 设置为 $B$）。

论文中使用链表实现。

分块优先队列维护两个链表 $D_0$ 和 $D_1$。$D_0$ 用来放 Batch Prepend 操作添加的 key，$D_1$ 用来放 Insert 操作添加的 key。$D_0$ 和 $D_1$ 是把块作为元素连接起来的链表。同一块内再维护一个链表，把块内的数据连接起来。（也就是链表套链表）。每个块都有一个属性：上界，块中所有的元素的 value 都不会超过这个上界。同时，对每个 key 维护其在链表中的指针（这里假设 key 不太大，可以按 node_map[key] = ptr 这样开桶维护，并且维护的开销也是 $O(1)$ 的）。

• 初始化时，$D_0$ 直接为空链表，$D_1$ 里面放入一个空的块，块的上界为 $B$。

• 插入时，首先看这个 key 之前是否已经被插入过了，如果是的话先直接删除（由于我们之前已经对 key 在链表中的指针进行了维护，所以这里无论是查找还是链表内删除，都是 $O(1)$ 的）。然后找到上界最小且大于要插入的 value 的块进行插入。同一个块内的 key 的 value 是无序的，所以直接插，$O(1)$。而找到要往哪个块插，需要我们先使用平衡树对每一个块的上界进行维护。后面我们会看到块的数量是 $O(\max\left \{ 1, \frac{N}{M} \right \})$ 的，于是查找要插的块的时间复杂度是 $O(\max\left\{ 1, \log \frac{N}{M} \right\})$。

  值得注意的是，当把一个元素从块内删除之后，不需要更新块的上界。如果块内元素全被删干净时，这个块没了，此时不得将块的上界从平衡树中删掉，那也还是只需要 $O(\max\left\{ 1, \log \frac{N}{M} \right\})$ 的时间复杂度，不影响整个插入操作的时间复杂度。

• 将元素插入到一个块之后，有可能这个块的元素数量大于了 $M$，于是需要对该块进行分割。分割的时候按 value 的中位数，分成两个 $\frac{M}{2}$ 的块。之所以这么做是为了确保每个块内的元素的数量位于 $\frac{M}{2}$ 和 $M$ 之间，即块内元素的数量是 $\Theta(M)$ 的，这样就能确保块的数量是 $O(\max\left \{ 1, \frac{N}{M} \right \})$ 的。

  寻找中位数使用线性寻找中位数算法：BFPRT，所以这个分割操作的时间复杂度是 $O(M)$ 的。

• 对于 Batch Prepend 操作，设批量插入 $L$ 个元素。如果 $L\le M$，那么直接在 $D_{0}$ 的最前面开一个块，把这 $L$ 个元素丢进去，时间复杂度大概是 $O(L)$ 的。反之，我们在 $D_0$ 最前面创建 $O(\frac{L}{M})$ 个块，然后对于这 $L$ 个元素不断地跑 BFPRT 算法按中位数切割（也就是先找中位数，把 $L$ 劈成两部分，然后对于每个部分再去找中位数，这样总共会劈成 $4$ 部分......这样一直分下去，直到劈成了 $O(\frac{L}{M})$ 部分）。这个不断切割的过程就像是一个递归树，层数为 $O(\log \frac{L}{M})$，同一层递归节点都要跑线性的 BFPRT 算法，所以总时间复杂度为 $O(L\log \frac{L}{M})$。

• 对于 Pull 操作，我们先从 $D_0$ 中从前往后收集块，直到收集到的元素数量大于 $M$ 或者没有更多块了。然后再从 $D_1$ 中进行类似的操作。把从两个链表中收集到的元素全部拿到一个集合 $S$ 中。如果 $|S| \le M$，那么非常好处理，这里不多说。反之，由于每一个块内元素大小不超过 $M$，所以最后 $S$ 内的元素数量不会超过 $M$ 太多，最多也就是 $4M$，即 $S=\Theta(M)$。然后我们可以直接在 $S$ 上面跑 BFPRT 算法，在 $\Theta(|S|)=\Theta(M)$ 的时间来把前 $M$ 小的元素找到，然后把这 $M$ 个元素逐个从删掉。逐个 $O(1)$ 删除也只会有 $O(M)$ 的时间。可能存在的问题是，删除时如果某个块变成空块了，就需要再付 $O(\max\left\{ 1, \log \frac{N}{M} \right\})$ 的块删除时间。这里我的理解是，你可以根据类似势能分析的思想，把这里删除块的时间复杂度算在插入块上。

总之，我们有：

操作	时间复杂度
Insert	$O(\max\left\{ 1, \log \frac{N}{M} \right\})$
Batch Prepend	$O(L\log \frac{L}{M})$
Pull	$O(M)$

2.4 Finding Pivots

我们上面提到过说，Finding Pivots 会把 $S$ 集合缩成 $P$，后续只需要在 $P$ 上做就是对的。我们来看 Finding Pivots 是怎么做的：

Finding Pivots 操作会进行类似于 Bellman ford 的 $k$ 轮松弛。和 Bellman ford 不同的是，Bellman ford 每轮松弛会松弛整个图的边，而这里的松弛只涉及到起点位于 $W_{i-1}$ 内的边，$W_{i-1}$ 表示上一轮松弛中成功松弛到的点。直观上理解，每轮松弛都相当于一圈一圈往外延展。这里的 $k$ 轮松弛还有种做 $k$ 层 BFS 的味道。

最终会得到两个东西，一个东西是 $W$ 集合，也就是这 $k$ 轮松弛下来能够到达的所有点，或者说是从 $S$ 内的点出发 $k$ 步以内能到达的所有点。一个是 $P$ 集合，表示后续的 BMSSP 算法只需要对 $P$ 内连出去的边进行松弛即可，相当于把 $S$ 缩小成了 $P$。我们把 $P$ 中的点称为 pivot。

关于 $P$ 集合是怎么来的，以及为什么只需要关心 $P$ 集合就是对的，接下来慢慢解释。

回忆起我们之前关于目标节点 $\widetilde{U}$ 的说法。上图中第 9 行的判断，只有当前距离小于 $B$ 的 $v$ 才加入到 $W$ 并且在下一轮松弛。当前距离大于 $B$ 的 $v$，最短路肯定更是大于 $B$ 了，那不归我们管，我们不放入 $W$ 中。

$\widetilde{U}$ 必然可以被分成两类：

• 从 $S$ 出发，走 $k$ 步就能 complete，这种点已经被我们加入到了 $W$ 中。

• 从 $S$ 出发，走 $k$ 步不能 complete，这种点可能需要再多走几步才能 complete。不过，至少我们可以知道，这样的点，从 $S$ 出发的最短路径上，前 $k$ 个点必然是已经在 $W$ 中且已经 complete 的了（即对应上面那一类）。

  于是 Finding Pivots 在最后，根据第 15 行的关系式，构建了一个”最短路树“（严谨点说应该是最短路森林）（最开始我们提出的第二个假设保证只会构成树而不会构成 DAG）。同时，这里的最短路树其实是假的，因为我们只做了 $k$ 轮松弛，无法保证被松弛的到的点已经是 complete 的（甚至 $S$ 中还有没 complete 的点）。也就是说，已经 complete 的点（也就是第一类的点）肯定在这个最短路树上，但是这个最短路树上还有没有 complete 的点，但这些点并不影响算法的正确性和复杂度。

  然后，对于每个最短路树，如果其内部节点数量大于 $k$ 的话，就将其加入 $P$ 集合作为 pivot。

  那么这里，对于走 $k$ 步不能 complete 的点，必然有：其最短路经过 pivot。

  于是同时也解释了为什么只需要看 $P$ 集合就是对的。原来在 $S$ 中但没在 $P$ 中的点，其树的大小小于 $k$，也就是从这个点出发，走不了 $k$ 步就没节点可以继续走了。走 $k$ 步不能 complete 的点必然不会经过这些点。

然后值得注意的是 $W$。虽然走 $k$ 步就能 complete 的点一定在 $W$ 中，但是 $W$ 中还有没 complete 的点，所以后面 BMSSP 算法还要再把这些点从 $W$ 中筛出来。$W$ 集合的产生既是顺手的事，也是必要的，$W$ 集合用来处理走 $k$ 步就能 complete 的点的最短路，$P$ 集合和后面的 BMSSP 算法用来处理走 $k$ 步不能 complete 的点的最短路。

然后回忆起 BMSSP 在最后说，如果 $W$ 内的点 $x$ 满足 $\hat{d}(x) < B'$，那么他就是 complete 的。我们有如下证明：假如说 $x$ 不是 complete 的，根据上面所说，$x$ 的最短路必然经过某个 pivot。而 BMSSP 在若干次循环之后，一定做到了把最短路小于 $B'$ 且经过 $P$ 的点 complete ，于是这里发生矛盾。

Finding Pivots 操作需要保证给到后续 BMSSP 算法的集合 $P$ 一定满足 $P\le \frac{|\widetilde{U}|}{k}$ 以保证后面 BMSSP 的时间复杂度。Finding Pivots 操作在最后有 $|W| \le |\widetilde{U} |$，同时由于我们 pivots 选择的规则，有 $k|P|\le |W|$，两个合起来，就有 $|P|\le \frac{|\widetilde{U} |}{k}$。

同时注意到，如果在某轮松弛之后，出现了 $|W|>k|S|$，而 $|W|\le |\widetilde{U} |$，于是我们有 $k|S| < |\widetilde{U}|$，$|S|<\frac{|\widetilde{U} |}{k}$，那么此时就说明 $S$ 其实本身规模就挺小的，直接把 $S$ 作为 $P$ 也可以接受，于是就直接把 $S$ 返回了。在这种情况下返回的 $W$ 我认为只是顺手的事了，貌似不太必要。

所以，$|W|=O(\min\left\{ k|S|, |\widetilde{U}| \right\})$，每轮松弛花费 $|W|$ 的时间，如果没有提前返回，最后也是花 $|W|$ 的时间生成集合 $P$。最后总的时间复杂度主要在多轮松弛上，为 $O(k|W|)=O(\min\left\{ k^2|S|, k|\widetilde{U}| \right\})$。

3. 正确性

首先是一堆数学符号：

$T(u)$ 表示以 $u$ 为根的最短路树。$T(u)$ 内的点的最短路经过 $u$。

$T(S)=\bigcup_{v\in S}T(v)$

$S^*=\left \{ v\in S: v \text{ is complete} \right \}$

显然有 $T(S^*)\subseteq T(S)$。

$T_{<B}(S) = \left \{ v \in T(S): d(v) < B \right \}$，即最短路经过 $S$ 且最短距离小于 $B$ 的点。$T_{<B}(S)$ 和上文提到的 $\widetilde{U}$ 是一致的。

$T_{\left [ b, B \right )}(S) = \left \{ v \in T(S): d(v) \in \left [ b, B \right\} \right\}$

Pull Minimum 引理

这个引理针对的是数据结构 $D$ （分块优先队列）的 Pull 操作。回忆 Pull 操作，它会把 $D$ 中的一个前缀 $S_i$ 取出来，并返回一个上界 $B_i$。也就是说，原本 $D$ 中当前距离小于 $B_i$ 的点都在 $S_i$ 中，当前距离大于等于 $B_i$ 的点都在 $D \setminus S_i$ 中。

Pull Minimum 引理宣称，如果所有最短路距离小于 $B$ 且还没 complete 的点都在 $T(D^*)$ 里，那么

• （a）所有最短路距离小于 $B_i$ （这里的 $B$ 是当前 BMSSP 的参数 $B$，所以必然有 $B_i < B$）且还没 complete 的点都在 $T(S_i^*)$ 中。

  这意味着，在前提条件成立的情况下，如果我们把 $D$ 以 $B_i$ 分成两部分，那么所有最短路距离小于 $B_i$ 且还没 complete 的点就归 $S_i$ 管了，$D$ 剩下的部分就不管了。也就解释了为什么 BMSSP 中 $S_i$ 和 $B_i$ 是满足子 BMSSP 第二个条件的。

• （b）如果 $B_i' < B_i$，那么 $T_{<B_i'}(D)=T_{<B_i'}(S_i)$

  这意味着，即使后续下层 BMSSP 是部分执行的，仅处理完了 $S_i$ 中最短路距离小于 $B_i'$ 的部分，但实际上是处理完了整个 $D$ 中最短路距离小于 $B_i'$ 的部分。

证明：

所有最短路距离小于 $B_i$ 且还没 complete 的点 $v$，根据引理的前提，其最短路必然是经过 $D$ 中某个已经 complete 的点 $u$ 。那么就有 $\hat{d}(u)=d(u)\le d(v)<B_i$，于是 $u$ 肯定是位于 $S_i$ 中的，于是 $v$ 肯定是位于 $T(S_i^*)$ 中的。（a）得证。

对于 （b），肯定有 $T_{<B_i'}(S_i)\subseteq T_{<B_i'}(D)$。然后对于 $v\in T_{<B_i'}(D)$ 有 $d(v) < B_i' < B_i < B$ ，那么根据 （a）有 $v \in T(S_i^*)$ 。设 $v$ 最短路经过 $S_i^*$ 中的点 $x$，那么就有 $\hat{d}(x) = d(x) \le d(v) < B_i'$，于是 $v$ 位于 $T_{<B_i'}(S_i)$ 中，即 $T_{<B_i'}(D) \subseteq T_{<B_i'}(S_i)$，于是（b）得证。

BMSSP 正确性

然后我们证明 BMSSP 的正确性，也就是证明：给定 $l$ 、$B$ 和集合 $S$，且 $S$ 满足两点大前提：

• $|S| \le 2^{lt}$
• 所有 $d(x) < B$ 且还没 complete 的 $x$ ，其最短路必须经过 $S$ 中某个已经 complete 的点，也就是 $T_{<B}(S^*) = T_{<B}(S)$

那么 BMSSP 一定会给出一个 $U$ 和 $B'$，满足经过 $S$ 且最短路距离小于 $B'$ 的点均在 $U$ 中且已经 complete。

证明：

使用双重数学归纳法。

对于 $l=0$，$S$ 中必然只有一个点 $x$（根据前提 1）。然后 BMSSP 的 BaseCase 会从 $x$ 开始做传统 Dijkstra，根据 Dijkstra 的正确性和前提 2，上述结论显然是成立的。

现在假设 $l-1$ 成立，我们要证明 $l$ 也成立。

在第 $l$ 层，我们会进行若干次循环迭代（BMSSP 算法第 $8$ 行）。我们令 $D_i$ 为第 $i$ 次循环前 $D$ 的样子。然后我们宣称下面两个命题在第 $i$ 次循环前必然是成立的：

• 所有最短路距离小于 $B$ 且还没 complete 的点，都位于 $T_{\left [ B_{i-1}',B \right)}(P)$ 中。$P$ 是第 $l$ 层最开始 Finding Pivots 操作得到的集合 $P$。

  这意味着...其实挺显然的，你可以想象 BMSSP 的这个循环主要是在松弛，然后松弛就意味着延申最短路树。而这个延申最开始就是从 $P$ 出发的。

• $T_{\left [ B_{i-1}', B \right )}(P) = T_{<B}(D_i) = T_{<B}(D_i^*)$

  这意味着，这些还没 complete 的点可以直接在 $D_i$ 上甚至是 $D_i^*$ 上处理。

为了证明上述两个命题成立，我们再用数学归纳法。

首先对于 $i=1$，我们已经在 Finding Pivots 操作中说过，所有最短路距离小于 $B$ 且还没 complete 的点（已经 complete 的位于 $W$ 集合了），最短路一定经过 $P$ 。由于 $T_{<B_0'}(P)$ 是空集，所以 $T_{<B}(P)=T_{\left[ B_0', B \right)}(P)$，命题一成立。

同时，必然有 $T_{<B}(P)=T_{<B}(P^*)$（也就是 $P$ 中所有没被 complete 的点，最短路经过 $P^*$。假如说不经过 $P^*$，那么根据 BMSSP 的第二个要求，必然是经过 $(S\setminus P)^*$。而根据 Finding Pivots 操作，最短路经过 $S\setminus P$ 的点必然已经 complete 掉并放入 $W$ 中了，否则被经过的点就不在 $S\setminus P$ 里了）。再加上初始时 $P = D_i$，命题二也成立。

假设对于 $i$ 成立。由于上述命题是在 $i$ 循环之前成立的，所以我们把 $i$ 循环的过程走一遍就会得到 $i+1$ 循环前的情况，也就能判断对于 $i+1$ 是否成立。

首先第 $i$ 个循环先从 $D_i$ 中取出了 $S_i$。然后去调用了 $l-1$ 层的 BMSSP。由于我们前面假设了 $l-1$ 层 BMSSP 成立，那么我们完全相信这个 BMSSP 的结果是对的。不过我们还需要确保满足 $l-1$ 层 BMSSP 的两个前提要求：

• 由于 $D$ 的 $M=2^{(l-1)t}$，所以 $|S_i| < 2^{(l-1)t}$，因此满足第一个前提
• 由于 $i$ 成立，根据命题二，所有最短路距离小于 $B$ 且还没 complete 的点一定位于 $T(D_i^*)$ 中，那么对于 $B_i<B$ 肯定也是成立的，于是满足 Pull Minimum 引理的前提。再根据 Pull Minimum 引理的（a），最短路距离小于 $B_i$ 且还没 complete 的点一定位于 $T(S_i^*)$ 中，因此满足第二个前提。

$l-1$ 层的 BMSSP 返回了一个 $U_i$ 和 $B_i'$。原来最短路距离位于 $[B_{i-1}',B_i')$ 的还没 complete 的点，即 $T_{[B_{i-1}',B_i')} (P)$，如今已经全部放入 $U_i$ 且 complete 了。由于 $i$ 成立，根据命题一，原来剩下的还要处理的点在 $T_{\left [ B_{i-1}',B \right)}(P)$ 中，现在 $T_{[B_{i-1}',B_i')} (P)$ 解决了，于是还剩下 $T_{[B_i', B)} (P)$ 没搞，于是命题一对于 $i+1$ 成立。

由于 $i$ 成立，根据命题二，$T_{\left [ B_{i-1}', B \right )}(P) = T_{<B}(D_i) = T_{<B}(D_i^*)$。首先，根据这个算法步骤我们可以看到，$D_i$ 中最小的元素必然也是大于 $B_{i-1}'$ 的，那么经过 $D_i$ 的距离小于 $B_{i-1}'$ 的最短路是不存在的，于是实际上有：$T_{\left [ B_{i-1}', B \right )}(P) = T_{\left [ B_{i-1}', B \right )}(D_i) = T_{\left [ B_{i-1}', B \right )}(D_i^*)$。三个集合相等，对应的区间也都是一样的，于是我们对这三个集合同时取距离位于 $[B_i,B)$ 的这部分，就有了 $T_{\left [ B_{i}', B \right )}(P) = T_{\left [ B_{i}', B \right )}(D_i) = T_{\left [ B_{i}', B \right )}(D_i^*)$。

要想证明命题二，我们可以试试能不能证明下两个子集关系：

• $T_{\left [ B_{i}', B \right )}(D_i^*) \subseteq T_{<B}(D_{i+1}^*)$
• $T_{<B}(D_{i+1})\subseteq T_{\left [ B_{i}', B \right )}(D_i)$

如果可以的话，我们就能有：

$$T_{\left [ B_{i}', B \right )}(P) \subseteq T_{\left [ B_{i}', B \right )}(D_i^*) \subseteq T_{<B}(D_{i+1}^*) \subseteq T_{<B}(D_{i+1}) \subseteq T_{\left [ B_{i}', B \right )}(D_i) \subseteq T_{\left [ B_{i}', B \right )}(P)$$

由于首位相等，于是中间的全部集合都是相等的，于是命题二对于 $i+1$ 也成立。

$D$ 中的元素大多数都是上轮循环继承到下轮循环。少数发生变动的元素是由于 Pull 操作和后面松弛完了之后再插入进去导致的。

对于子集关系一，取一个节点 $y\in D_i^* \setminus D_{i+1}^*$。这个节点在上一轮不在下一轮，说明他被 Pull 出去了。同时他还没由于 BatchPrepend 加回到这一轮，说明 $\hat{d}(y) < B_i'$，因此 $y \in U_i$。现在任取 $x\in T_{\left [ B_{i}', B \right )}(y)$，由于 $d(x)\ge B_i'$，所以 $x$ 肯定不在 $U_i$ 中。考虑从 $y$ 到 $x$ 的最短路径，$y\in U_i$ 而 $x\notin U_i$，说明路径上必然存在一条边 $(u,v)$ 使得 $u\in U_i$ 而 $v\notin U_i$。我们后面对 $U_i$ 内所有点的出边都进行了松弛，且 $(u,v)$ 在最短路径上，因此 $(u,v)$ 必然得到了有效松弛。而 $v$ 必然是位于了 $D_{i+1}^*$ 中的，而 $x$ 是 $v$ 的下游，因此 $x\in T(v) \subseteq T(D_{i+1}^*)$，得证。

对于子集关系二，还是取一个节点 $y\in D_{i+1}\setminus D_i$。这个点不在上一轮而在下一轮，这是怎么来的？是因为我们在处理 $U_i$ 的时候松弛了边 $(u,y)$，并且这个松弛是有效松弛，所以就被加进 $D$ 了。我们取最后一次让 $y$ 有效更新的边 $(u, y)$，然后会分成如下几种情况：

• 如果 $y$ 是 complete 的，由于 $(u, y)$ 是 $y$ 的最后一次有效松弛，那么一定有 $y\in T(u)$，即 $y$ 的真实最短路是从 $u$ 来，且 $d(y) \ge B_i'$。又因为 $u\in U_i = T_{<B_i'}(D_i)$，所以 $y \in T_{\left [ B_{i}', B \right )}(D_i)$
• 如果 $y$ 不是 complete 的，根据已经证明的 $i+1$ 轮成立的命题一，这样的 $y \in T_{[B_i', B)}(P)$ ，然后由对于 $i$ 轮成立的命题二，$y\in T_{[B_i', B)}(D_i)$

无论是哪种情况，都有 $y \in T_{\left [ B_{i}', B \right )}(D_i)$。$D_{i+1}$ 出发的某个路径可能是从 $y$ 出发的，但是 $y$ 又是从 $D_i$ 出发的，所以 $T_{<B}(D_{i+1})\subseteq T_{\left [ B_{i}', B \right )}(D_i)$ 得证。于是关于循环的两个命题得证。

然后我们可以看到，假如说 $l$ 层 BMSSP 进行了 $q$ 次循环，那么这 $q$ 次循环实际会收集 $q$ 个 complete 的点的集合：$U_1, U_2, \dots, U_q$，其中 $U_i = T_{\left [ B_{i-1}',B_i' \right)}(P)$（根据循环的命题一）。我们看到我们其实是把 $P$ 出去的距离小于 $B'$ 的最短路，不重不漏地分成了 $q$ 个部分，并且全部 complete 掉了。

现在还差一步。对于 $S\setminus P$ 出去的最短路，这些点已经在 Finding Pivots 操作中就 complete 了，BMSSP 在最后也对其进行了收集。因此 BMSSP 是正确的。

4. 时间复杂度

BMSSP 的过程构成了一个递归树。我们设递归树上的某个节点 $x$ 的参数是 $l_x$ 、$B_x$ 和 $S_x$，目标节点为 $\widetilde{U}_x$，Finding Pivots 操作获得的集合为 $P_x$，BMSSP 返回 $B_x'$ 和 $U_x$。

首先，在递归树的同一深度上，所有节点 $x$ 返回的集合 $U_x$ 是互不相交的，这一点已经在 BMSSP 正确性的部分中提到过了。因此同一层的 $|U_x|$ 加起来应该是小于等于 $n$ 的。

由于我们之前说顶层 BMSSP 取 $l=\left\lceil \frac{\log n}{t} \right\rceil$ ，所以整个递归树的层数是 $\frac{\log n}{t}=O(\log ^{\frac{1}{3}} n)$ 的。

$|P|$ 规模

对于 Finding Pivots 操作返回的 $P$，有 $|P| \le \frac{|\widetilde{U}|}{k}$。进一步，我们还有：

• 如果 $x$ 是成功执行的，就有 $U = \widetilde{U}$，那么 $|P| \le \frac{|U|}{k}$
• 如果 $x$ 是部分执行的，$|U| \ge k2^{lt} \ge k|S|$，因此 $|P| \le |S| \le \frac{|U|}{k}$

总之就是 $|P| \le \frac{|U|}{k}$。

$|U_i|$ 规模

完成完 BMSSP 之后，$|U| \le 4k2^{lt}$。如果 BMSSP 部分执行的话，我们还有 $|U| \ge k2^{lt}$。

对于后者显然成立，下面证明前者：

对 BMSSP 的层数 $l$ 使用数学归纳法。$l=0$ 时，朴素的 Dijkstra 每次循环都只往 $|U|$ 中加一个点，加到 $|U| \ge k2^{lt}$ 就立刻停止。所以 $|U| \le 4k2^{lt}$ 是显然成立的。

假设对于 $l-1$ 成立。

设 BMSSP 一共进行了 $q$ 次循环，那么在第 $q$ 次循环之前，必然有 $|U_{\text{before\_q}}|<k2^{lt}$。

第 $q$ 次循环，会调用下层 BMSSP，得到返回结果 $U_q$，并把 $U_q$ 加进 $U$ 里面。由于对于 $l-1$ 成立，所以 $|U_q|\le 4k2^{(l-1)t}$。

循环结束之后，还会对 $W$ 集合进行过滤得到 $W_{\text{filtered}}$，并把 $W_{\text{filtered}}$ 加入到 $U$ 里面。根据 Finding Pivots 的性质，$|W|\le k|S|$，又因为 BMSSP 的前提条件 $|S| \le 2^{lt}$，因此有 $|W_{\text{filtered}}| \le |W| \le k2^{lt}$（这里就体现出当时 Finding Pivots 控制 $W$ 规模的重要性了）

最终返回大小

$$\begin{align} |U| &\le |U_{\text{before\_q}}| + |U_q| + |W_{\text{filtered}}| \\ &\le k2^{lt} + 4k2^{(l-1)t} + k2^{lt} \\ &= 2k2^{lt} + 4k\cdot \frac{2^{lt}}{2^t} \end{align}$$

由于 $t = \left \lfloor \log^{\frac{2}{3}}n \right \rfloor$，对于足够大的 $n$，显然有 $2^t\ge 4$，因此 $|U| \le 2k2^{lt} + k2^{lt} = 3k2^{lt} \le 4k2^{lt}$，证毕。

分块优先队列的时间复杂度

在第 $l$ 层的 BMSSP 中，有 $M=2^{(l-1)t}$。然后观察算法过程，$D$ 中元素一部分来自 $P$，另一部分来自松弛操作加入的点。根据出度为常数的假设，松弛操作最多会进行 $O(|U|)$ 次，而 $|U|$ 受到 $k2^{lt}$ 的限制。同时由于 $|P| \le \frac{U}{k}$ ，因此 $D$ 最多会被塞入 $N = O(k2^{lt})$ 个点。

• Insert：时间复杂度为 $O(\max\left\{ 1, \log \frac{N}{M} \right\})$。带入 $N$ 和 $M$，有 $O(\log \frac{k2^{lt}}{2^{(l-1)t}})=O(\log (k2^t)) = O(t+\log k)$，由于 $\log k = \log (\log ^{\frac{1}{3}}n) \ll t$，所以可以认为单次 Insert 操作时间复杂度为 $O(t)$。
• BatchPrepend：时间复杂度为 $O(L\log \frac{L}{M})$。而批量前插的元素集合 $K$ 的大小是 $O(|U_i|) = O(k2^{lt}) = O(kM)$，因此均摊到每个元素上的时间复杂度为 $O(\log \frac{L}{M}) = O(\log \frac{kM}{M}) = O(\log k)$。
• Pull：拉取 $M$ 个的时间复杂度为 $O(M)$，那么均摊到每个元素上，时间复杂度为 $O(1)$。

Lemma 3.11

$\min\left\{ k|S|, |\widetilde{U}| \right\} \le |U|$

其中 $\widetilde{U}$ 是我们的 BMSSP 理论上想要处理的所有目标（具体定义在 Finding Pivots 那里），$U$ 表示 BMSSP 实际处理的节点数量。如果 BMSSP 成功执行了，那么 $U=\widetilde{U}$。如果部分执行，则 $U\subset \widetilde{U}$。

证明：

如果成功执行了，那么 $U=\widetilde{U}$，上式显然成立。

如果没成功执行，必然有 $|U| \ge k2^{lt}$。根据 BMSSP 的第一个前提，$|S| \le 2^{lt}$，因此 $k|S| \le k2^{lt} \le |U|$，证毕。

---

然后整个算法的过程的时间开销主要分成如下几个部分：

（1）全图所有 FindPivots 开销

递归树某个节点 $x$ 的时间复杂度为 $O(\min\left\{ k^2|S_x|, k|\widetilde{U}_x| \right\}) = O(k|U_x|)$

同一层的所有节点开销加起来，为 $O(kn)$

递归树一共 $O(\log ^{\frac{1}{3}} n)$ 层，于是该部分总耗时为 $O(n\log^{\frac{2}{3}}n)$。

（2）Pivots 插入数据结构 $D$ 中开销

由于 $|P| \le \frac{|U|}{k}$。因此把 $P$ 插入到数据结构 $D$ 的开销是 $O(\frac{|U_x|}{k} \cdot t)$。

同一层全部节点加起来的总开销为 $O(\frac{nt}{k})$。

整个递归树在该部分的开销为 $O(\frac{nt}{k}) \times O(\log ^{\frac{1}{3}} n) = O(n\log^{\frac{2}{3}}n)$。

（3）边松弛导致直接插入开销

如果在某次松弛中，一条边 $(u,v)$ 让 $v$ 直接触发了 Insert 操作，说明 $v$ 经过松弛后 $B_i \le \hat{d}(v) = d(u) + w_{uv} \le B$。事实上，每条边，在整个算法的过程中，只会触发一次直接 Insert 操作。

证明：

首先由于 BMSSP 得到的 $U_i$ 都是不交的，所以在当前 BMSSP 的过程中，$u$ 只会被扫到一次，因此一条边也只会被松弛一次，也最多只会触发一次 Insert 操作。

假如 $u$ 所在的 $U_i$ 是由某个子 BMSSP 得到的，该子 BMSSP 的参数 $B$ 是 $B_i$。在该子 BMSSP 中，假如说 $u$ 又作为某个 $U_i$ 内的点往外松弛的话，遇到 $(u,v)$ 这条边之后，由于 $B_i \le d(u) + w_{uv}$，所以根本不会触发松弛，也就不会触发 Insert 操作。

$u$ 在调用当前 BMSSP 的父节点里往外松弛的时候，如果遇到了 $(u,v)$ 这条边，由于 $d(u) + w_{uv} \le B$，这里的 $B$ 是当前 BMSSP 的上限，却是父 BMSSP 想要触发 Insert 的下限，因此不会触发 Insert 操作。

边的数量是 $\Theta(n)$ 的，所以总的时间复杂度为 $O(nt) = O(n\log^{\frac{2}{3}}n)$。

（4）BatchPrepend 开销

每次 BatchPrepend，单个元素的均摊耗时为 $O(\log k)$。最坏情况下，整个一层得到的所有 $U_i$ 内的点松弛出去的边都会导致终点被加入到集合 $K$ 从而被 BatchPrepend 到 $D$ 中。由于 $U_i$ 无交，以及出度为常数的假设，所以被 BatchPrepend 的点的数量是最多 $O(n)$ 的。一共是 $O(\log ^{\frac{1}{3}} n)$ 层，因此总耗费时间为 $O(n\cdot \log(\log^{\frac{1}{3}} n) \log ^{\frac{1}{3}} n)$，比 $O(n\log ^{\frac{2}{3}}n)$ 小，可以忽略不计。

于是我们就得到了 $O(n\log^{\frac{2}{3}} n)$ 的时间复杂度。

5. 不失一般性

上面所有的分析都是在论文的两个假设上进行的。下面我们说明论文的这两个假设不失一般性：

常度数图

对于任意的图 $G$，都可以进行如下的转换，得到图 $G'$。图 $G'$ 满足入度和出度最多只有 $2$，且 $G$ 中的最短路在 $G'$ 中仍得到保留：

• 对于所有的节点 $v$，假如说他有个相邻节点 $w$（无论这个节点是从 $v$ 出去的还是指向 $v$ 的），我们都在 $G'$ 中对应一个节点 $x_{vw}$。所有关于 $v$ 的这种节点都用边权为 $0$ 的变强连通起来（比如构成一个环）。
• 然后对于 $G$ 中的所有边 $(u,v)$，都加一个从 $x_{uv}$ 指向 $x_{vu}$ 的有向边，边权为 $w_{uv}$。

比如：

转为：

我们可以看到，红圈内的点相当于原图中的一个点（相当于我们把原图中的点拆开了），而同一个圈内的节点是强连通，且互相之间的距离为 $0$，因此最短路得到了保留。而且从这个构造过程中也能发现，点入度和出度最多只有 $2$，且 $n'=\Theta(m')=\Theta(m)$（$n'$ 和 $m'$ 为 $G'$ 的点和边的数量，$m$ 为 $G$ 的边的数量）

每个点的最短路均不同

如果两个最短路的长度是相同的，我们还可以再去比较跳数（即经过的点数），跳数相同则继续比最短路终点编号，终点编号相同再去比较倒数第二个点的节点编号，还相同则继续比较倒数第三个节点的编号....这样一直比下去肯定能决出胜负，否则的话这两个最短路就是完全一致的。

这样的比较看起来是 $O(n)$ 的。但其实论文中的最短路比较一共分成两种情况：

• 当对边 $(u,v)$ 进行松弛时，此时 $v$ 原来的最短路可能是这样 $s\rightarrow \dots \rightarrow x \rightarrow v$，现在要尝试的最短路是 $s\rightarrow \dots \rightarrow u \rightarrow v$。由于我们不考虑重边，因此 $x$ 和 $u$ 必然是不同的，也就是说即使两条最短路的距离和跳数都相同，终点也相同（显然一定是），倒数第二个点也不同。

• 当比较两个不同终点的最短路，比如 $\hat{d}(u)$ 和 $\hat{d}(v)$（$u\neq v$）时，即使距离和跳数都相同，也能在终点编号这里决出胜负。

  这种情况一般是 BaseCase 中的堆以及分块优先队列中使用。

  不过可能出现这种情况：要插入的 key 已经在分块优先队列中存在了，此时就需要终点相同的最短路的比较。而算法中都是成功松弛之后才会把 key 插入数据结构，那么根据第一种情况，这个 key 所对应的最短路的倒数第二个节点必然是不一样的。

所以我们可以把终点为 $u$ 的最短路视为一个四元组 $(d(u),hop(u),u,pred(u))$，其中 $d(u)$ 为最短路，$hop(u)$ 为最短路跳数，$pred(u)$ 为 $u$ 最短路的前驱，然后比较的时候直接按这个四元组比较就可以了。维护 $hop(u)$ 和 $pred(u)$ 就跟维护 $d(u)$ 一样。可以 $O(1)$ 做。

6. 复现

代码在 https://github.com/caiwen666/hnu-algo 的 src/algorithms/bmssp 中：

• const_graph.rs 实现了一般图到常度数图的转化。
• path_dist.rs 实现了上面所说的路径四元组的比较。整个算法的距离都是用 PathDist 这个类型来表示的。
• block_ds.rs 实现了分块优先队列。
• mod.rs 实现了算法的主体。

tests/bmssp.rs 提供了对 bmssp 的测试，benches/bmssp.rs 提供了对 bmssp 的性能测试。

复现的时候需要注意：

• 分块优先队列的 $D_1$ 需要保证时刻有一个上界是 $B$ 的块。这也就意味着，上界为 $B$ 的块内的点如果被删空了，那么是不能删掉这个块的，还需要保留。

• 论文中分块优先队列的块分裂使用 BFPRT 来找中位数，但显然直接手搓一个 BFPRT 的话常数肯定爆炸了。好在 Rust 标准库里的 select_nth_unstable_by_key 也能平均做到 $O(n)$。

  同理，Batch Prepend 递归搞 BFPRT 的话常数估计也爆了，所以我这里的实现是直接使用 sort_unstable_by_key 。

其他的地方基本就是照着论文上的伪代码搓。https://github.com/caiwen666/hnu-algo/pull/1 里展示了复现的过程。

复现的第一版代码跑了 3.8s，大概比 Dijkstra 慢了 30 倍。。。显然常数太大了。跑了个火焰图，发现 PathDist 的比较过程是热点，于是把 path_dist.rs 那里的四元组压成了一个 u128 和一个 u32，这样从原来的比较四次优化成了比较两次。同时还稍微搞了下内存复用。不过只是优化到了 3.6s。

然后又跑火焰图，发现计算哈希的开销比较大。最开始的代码用了不少 HashMap 和 HashSet，而 Rust 默认使用的 SipHash 为了保证安全性，计算速度比较慢。我的 HashMap 和 HashSet 的 key 都是节点编号，不太需要高级的哈希算法，于是换成了速度更快但是安全性比较差的 FxHash，把时间优化到了 2.8s。

后来实在没活整了，就直接让 Claude Opus 4.6 给我优化了一下，把时间优化到了 1.6s。我在 review 的时候顺便学习了一下，AI 主要干了这么几件事：

• 将 PathDist 重新布局

  原来是 dis(64) + hop(32) + end(32) 合成一个 u128，然后 pred 单独一个 u32

  现在变成了 dis(64) 单独拿出来，hop(22) + end(21) + pred(21) 合成一个 u64

  在底层 u128 可能还是分高 64 位和低 64 位两次比较的，而如今两个 u64 应该是稍微好点的。同时由于把 hop、end 和 pred 缩成了 21 位，所以现在算法只能跑在点数在 2e6 以内的图上。

• 将常度数图变为 CSR 表示

  这样的话所有的边在内存中都是连续的，可能可以提高缓存的命中率。

• Finding Pivots 在建最短路森林的时候，原来是使用 HashMap<usize, Vec<usize>>，现在是使用链式前向星，减少了内存分配。

• 把 HashMap 和 HashSet 能砍的全都砍了：

  • BMSSP 中的 u_set 变为 Vec，然后使用公共的内存池，通过在桶中发放时间戳来判断一个点是否已经在集合中了。

    但是由于 BMSSP 是递归的，所以公共内存池可能又被子 BMSSP 占用。AI 利用了子 BMSSP 的 U 是没有交集的这个性质，确保了子 BMSSP 不会破坏父 BMSSP 的 u_set 标记。

  • Finding Pivots 中的 w_set 也是变为 Vec，然后使用公共的桶来判断一个点是否已经在集合里了。

  • 在生成 p_set 的时候应该没有重复节点，所以 p_set 直接改用 Vec。

  • BlockDs 里面的 key 到 node_id 的映射，在原来是需要每个 BlockDs 实例里面都建 HashMap。AI 的思路是复用一个桶。这个桶建在 BMSSP 实例里面。

    首先第一个问题，这个复用的桶需要在 BlockDs 销毁的时候将其还原。AI 的思路是在 block_ds 里面维护一个 Vec，存储所有插入过的 key，还原的时候就根据这个 Vec 复位。

    第二个问题是，父 BMSSP 在调用子 BMSSP 的时候，父 BMSSP 会建一个 BlockDs，子 BMSSP 也会建一个 BlockDs，这就需要我们需要准备多个可以复用的桶。这中间可能遇到 Rust 的 mut 引用检查的阻碍，需要 unsafe。

• 还有其他的能内存复用的地方就复用。

• 预留容量，比如 BaseCase 中的 u_set 大小大概是 $k+1$ ，那么就让 u_set 的 Vec 预留 $k+2$ 的空间。

• 使用占用内存更小的类型。这样主要是减小缓存行的压力

  比如点的编号基本都从 usize 变为 u32 了

  除此以外，AI 还把要用 Option 的地方直接用 u32::MAX 来代替 None。u32 是 4 字节，但是 Option 需要给加 Tag，对齐完了之后，Option<u32> 就是 8 字节了。

使用洛谷 Cyaron 造了四组数据：

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/env python

from cyaron import * # 引入CYaRon的库

_n = ati([0, 10, 1E3, 5E5, 5E5])
_m = ati([0, 30, 2E4, 1E6, 1E6])

for i in range(1, 5):
    test_data = IO(file_prefix="ssp", data_id=i)

    n = _n[i] # 点数
    m = _m[i] # 边数
    s = 1

    if i == 4:
        graph = Graph.hack_spfa(n, self_loop=False, directed=True, repeated_edges=False, weight_limit=int(1E9))
        m = int(1.5 * n)
    else:
        graph = Graph.graph(n, m, self_loop=False, directed=True, repeated_edges=False, weight_limit=int(1E9))
    test_data.input_writeln(n, m, s)
    test_data.input_writeln(graph)
    test_data.output_gen("ssp_std.exe")

（本来第四组数据想卡 spfa，结果发现洛谷的 Cyaron 的 hack_spfa 是假的，相关 issue 已经挂了一万年了）

在腾讯云 C6.LARGE8 实例上跑了下 benchmark，对比了一下 Dijkstra，Spfa 和 BMSSP：

	Case1	Case2	Case3	Case4
Dijkstra	268.89 ns	161.11 µs	106.43 ms	8.4268 ms
Spfa	176.81 ns	141.64 µs	43.333 ms	5.0149 ms
BMSSP	19.683 µs	19.349 ms	1.3813 s	265.75 ms

可以看到，BMSSP 即使理论上比 Dijkstra 的时间复杂度低，但是由于算法过程比较复杂，常数太大，实测还是比 Dijkstra 慢十好几倍。

实际上理论上，不考虑任何常数的影响，BMSSP 也就比 Dijkstra 快 $\log^{\frac{1}{3}} n$ 倍，当 $n=10^6$ 时，理论上也就快 $2.7$ 倍，但是 BMSSP 的代码实现的常数肯定比 Dijkstra 高了不止 $3$ 倍，得到这样的结果是不意外的。但是复现这个论文是算法课作业，于是就图一乐。