如有错误，欢迎指出。

大概是论文的翻译，我懒得实现了（咕咕咕，咕）万一有人实现出来比 $\text{dijkstra}$ 快呢。

原文网址：A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs

大意就是非负实数边权的期望复杂度比原版 $\text{Dijsktra}$ 低的无向图单源最短路，只使用比较和 $+$，默认你会 斐波那契堆。

符号约定

$G=(V,E)$ 表示图，$V$ 表示点集，$E$ 表示边集，不失一般性，$G$ 是连通图。

我们认为图是比较稀疏的，也就是 $m=o(n\log n)$，否则这个算法和 $\text{dijkstra}$ 就没有什么区别了。

$s$ 表示起点，$d(x,y)$ 表示 $x$ 到 $y$ 的最短距离，特别地 $d(t)=d(s,t)$。因为是无向图，总有 $d(x,y)=d(y,x)$。

$w(x,y)=w_{x,y}$ 表示 $x$ 与 $y$ 之间的边权。

用 $w$ 松弛 $d(x,y)$ 表示 $d(x,y)\leftarrow\min(d(x,y),w)$。

用 $x\rightarrow y\rightharpoonup z\rightarrow w$ 表示一条 $x$ 到 $w$ 的路径，中途经过 $y,z$，并且路径上 $y$ 的下一个点是 $z$。

为什么可以这么快

你不要骗我，基于比较的最短路算法有下界 $O(m+n\log n)$。

复杂度下界的结论来自 A Shortest Path Algorithm for Real-Weighted Undirected Graphs | SIAM Journal on Computing。原文的结论更强一点，给出的下界是 $O(m+n\min\{\log\log r,\log n\})$，这里 $r$ 是和值域相关的，我们这里考虑实数边权所以不用管。

但是原文的做法大概是说存在一种点的排列，使得你的复杂度一定可以达到这个下界，但是这里是随机化做法，所以期望复杂度可以更低。

准备工作：图的三度化

考虑一个点的邻居集合 $N(u)=\{v:(u,v)\in E\}$，我们把点 $u$ 变成一个环，环上的边权都是 $0$，环上每个点都连接一个原本的 $v$，容易发现这样不影响 $d$。

如此，我们就得到一个有 $O(m)$ 条边和 $O(m)$ 个点的图，并且每个点的度数都不超过 $3$。

随机最短路

分块

奇怪的翻译

分块最短路

$\text{Dijkstra}$ 是一个很好的算法，我们可以考虑随机撒点跑 $\text{Dijkstra}$，然后再维护散点到这些点的距离，最后计算出所有的 $d$。

形式化地，我们以一个概率 $p$ 把点加入 $R$，只有 $R$ 中的点会被加入堆中。

图分块与球

对于散点，一个很 $\text{naive}$ 的想法就是把其归到距离最近的 $u\in R$ 所属的“块”中（原文是 $\text{bundle}$，我不知道怎么翻译比较好）。

其实这个 $\text{trick}$ 还是挺常见的，对于一个点 $v$，我们把 $R$ 中距其最近的点记为 $b(v)$，形式化地，$\forall r\in R,d(v,r)\geqslant d\big(v,b(v)\big)$。同时，我们额外定义球：$\text{Ball}(v)=\{u:d(v,u)

然后定义一个点所在的块为 $\text{Bundle}(u)=\{v:b(v)=u\}$。我们认为 $b(u)=u,\forall u\in R$，显然，所有 $\text{Bundle}$ 构成了 $V$ 的一个划分。

球的求解

注意到在 $\text{Dijkstra}$ 算法中，每次从堆顶取出的点已经求得了最短路，于是 $\forall v\not\in R$，都跑一遍 $\text{Dijkstra}$，当堆顶取出的点在 $R$ 中时就停止，这个点就是 $b(v)$。

我们记对于 $v$ 求解 $\text{Ball}(v)$ 时堆中压入的元素集合为 $S_v$，那么显然 $\text{Ball}(v)\subset S_v$，因为 $b(v)$ 和堆中余下的元素不属于 $\text{Ball}(v)$。因为 $R$ 是逐点随机选的，于是 $\mathbb{E}(R)=mp,\mathbb{E}(|S_v|)=\frac1p$。

因为我们已经把 $G$ 三度化了，所以每次只会加入 $O(1)$ 个点。于是堆中的元素个数也是 $O(|S_v|)$。

于是求解球的复杂度就是

$$ \begin{align*} \sum_{v\not\in R}O(|S_v|\log|S_v|)&=O(\frac mp\log\frac 1p) \end{align*} $$

算法思路

整点的最短路

整体的思路就是随机撒点跑普通 $\text{Dijkstra}$，然后跑了一个点 $x$，就要把其对应的块 $\text{Bundle}(x)$ 中的点的最短路都处理好。

首先，我们考虑 $r\in R$ 的点。

假设有一条路径 $p:s\rightarrow x\rightarrow r$，那么 $|p|\ge d(s,x)+d(x,r)$。

根据 $\text{Bundle}$ 的定义，$d(x,r)\ge d(x,b(x))$，于是 $|p|\ge d(s,x)+d(x,b(x))$。因为 $s\rightarrow b(x)$ 的最短路不一定经过 $x$，所以 $|p|\ge d(s,x)+d(x,b(x))\ge d(s,b(x))$。

然后我们取 $p$ 是 $s\rightarrow r$ 的最短路，那么 $|p|=d(s,r)\ge d(s,b(x)),\forall x\in p$，也就是对于路径上的点 $x$，都有 $d(b(x))\le d(r)$。

又发现 $\forall x,b(x)\in R$，根据每个块都会被处理好的假设，到 $r\in R$ 的最短路上的点都会被处理好。

上面证明了，只要散点的最短路求出，整点 $r$ 的最短路只能由已经处理好的点贡献。

非常 $\text{naive}$ 的想法就是枚举所有可能的边，这样的边只能来自 $\text{Bundle}(r)$ 和 $x\in\text{Bundle}(r),N(x)$。

对于 $x\in \text{Bundle}(r)$，用 $d(x)+d(x,r)$ 松弛 $r$ 即可。

对于 $x\in \text{Bundle}(r),y\in N(x)$，枚举 $z\in N(y)$，如果 $z\in\text{Bundle}(r)$，就用 $d(y)+w(y,z)+d(z,r)$ 松弛 $r$。（注意到 $y$ 只会有 $O(1)$ 个邻居）

散点的处理

对于 $v\not\in R$，如果 $s\rightarrow v$ 的最短路上的点 $x$ 都满足 $d(b(x))\le d(b(v))$，那么和上面进行一样的处理就可以了。

假设最短路 $p$ 上有至少一个点 $y$ 满足 $b(y)\ne b(v),d(b(y))\ge d(b(v))$。取等是因为相同距离的 $r\in R$ 弹出堆顶的时间也是不一样的，但如果 $r_1,r_2\in R$，这个差异不会影响答案，除非 $d(r_1,r_2)=0$，但这样的话 $r_1,r_2$ 可以缩成一个点。

同时，这样的最短路 $p$ 至少要满足 $|p|=d(s,v)< d(s,b(v))+d(b(v),v)$。因为 $b(v)\in R$，走到 $b(v)$ 是可以不经过 $y$ 的，$b(v)\rightarrow v$ 的最短路也在 $\text{Ball}(v)$ 内。如果 $\ge$ 的话则和假设矛盾。

根据最短路的假设，我们知道 $d(s,v)=d(s,y)+d(y,v)$，也就是 $d(y,v)=d(s,v)-d(s,y)$。

根据假设，有 $d(s,v)

可得

$$ \begin{align*} d(y,v)&=d(s,v)-d(s,y)\\ &<\Big(d\big(s,b(v)\big)+d\big(b(v),v\big)\Big)+\Big(d\big(y,b(y)\big)-d\big(s,b(y)\big)\Big)\\ &=\big(d(s,b(v))-d(s,b(y))\big)+d(b(v),v)+d(y,b(y))\\ &\le d(b(v),v)+d(y,b(y)) \end{align*} $$

假设 $z_1$ 是 $p:s\rightarrow y\rightarrow v$ 上最后一个满足 $d(y,z_1)\le d(y,b(y))$ 的点。根据 $\text{Ball}$ 的定义，$z_1\in\text{Ball}(y)$。

如果 $z_1=v$，那么我们只需要用 $N(v)$ 中的点松弛 $v$ 就可以了。

否则，$p$ 可表示为 $s\rightarrow z_1\rightharpoonup z_2\rightarrow v$，那么根据假设有 $d(y,z_2)>d(y,b(y))$。

因为 $p$ 是最短路，所以有 $d(y,v)=d(y,z_2)+d(z_2,v)\le d(b(v),v)+d(y,b(y))$，立刻得到 $d(z_2,v)

于是根据 $\text{Ball}$ 的定义，我们知道 $z_2\in\text{Ball}(v)$。这样的话我们维护 $d(v)$ 时枚举 $z_1,z_2$ 即可。

Bundle Dijkstra

算法流程

总结一下上面的思路，我们稍微简化一下，可能还处理了一下正确性的细节，可以得到算法流程（已经三度化并求解 $\text{Bundle}$ 和 $\text{Ball}$）：

首先，置 $d(s)=0,\forall x\ne s,d(x)=+\infty$，把 $R$ 中的节点加入斐波那契堆（如果是 $m=O(n)$ 的稀疏图，用别的堆也没有关系）。

然后，每次取出堆顶 $u$：

1. $\forall v\in\text{Bundle}(u)$，用 $d(s,u)+d(u,v)$ 松弛 $v$（$d(u,v)$ 在分块时已经求出），然后 $\forall z_2\in\text{Ball}(v)$，用 $d(s,y)+d(y,v)$ 松弛 $v$，再 $\forall z\in N(y)$，用 $d(s,z)+w(z,y)+d(y,v)$ 松弛 $v$。
2. 在上面的步骤完成后，$\forall v\in\text{Bundle}(u),\forall y\in N(v),\forall z\in\text{Ball}(y)$，用 $d(s,v)+w(v,y)$ 松弛 $y$，用 $d(s,v)+w(v,y)+d(y,z)$ 松弛 $z$。
3. 第二步中，松弛任意点 $x$ 的同时用 $d(s,x)+d(x,b(x))$ 松弛 $b(x)$。

   正确性证明

   要维护的性质

不妨设从 $R$ 中取出的第 $i$ 个点为 $u_i$，$u_0=s$，我们只需要证明下面 $3$ 条性质：

1. 当 $u$ 从堆顶被取出时，$d(u)$ 已经是正确的
2. 同普通 $\text{Dijkstra}$ 一样，满足 $d(u_i)\ge d(u_j)$ 当 $i\ge j$ 时。（注意这里是临时维护的答案，不是真的最短距离）
3. 进行 $\text{Bundle Dijkstra}$ 后，$\text{Bundle}(u_i)$ 中的点都确实是最短路

考虑数学归纳法。

初始情况

首先，$u_0=s$，$\text{Bundle}(u_0)$ 中的点在求解 $\text{Bundle}$ 时就已经处理好了，性质 $1,3$ 显然正确。

然后此时只有 $d(s)=0$，$\forall u_k\ne s,d(u_k)=+\infty$，于是性质 $2$ 也成立。

性质 1

假设 $u_0\ldots u_{k-1}$ 都处理好了，下面证明对于 $u_k$，性质 $1$ 成立。

设 $\text{B}_i=\bigcup_{j=0}^i\text{Bundle}(u_j)$，那么 $B_{k-1}$ 就是已经处理好的点的集合，如果 $s\rightarrow u_k$ 的最短路只经过了 $B_{k-1}$ 中的点，那么显然是对的。（因为就和普通 $\text{Dijkstra}$ 没有区别了）

设 $p:s\rightarrow x\rightharpoonup y\rightarrow u_k$，其中 $x$ 是 $p$ 上最后一个满足 $x\in B_{k-1}$ 的点。

注意到 $d(y,b(y))\le d(y,u_k)$（如果 $b(y)=u_k$，成立；否则，根据 $\text{Ball}$ 的定义，成立），于是

$$ \begin{align*} d(b(y))&\le d(y)+d(y,b(y))\\ &\le d(y)+d(y,u_k)\\ &\le d(u_k) \end{align*} $$

根据假设，可以知道 $b(y)=u_l,l\ge k$，根据假设有 $d(b(y))\ge d(u_k)$。

于是上面不等式链中的不等号全部应该是等于，那么 $d(b(y))=d(u_k)=d(y)+d(y,b(y))$ 并且 $d(y,b(y))=d(y,u_k)$。根据算法步骤 $2$，$b(y)$ 会作为 $z$ 被枚举到。所以，如果此时 $d(u_k)$ 不正确，那么先弹出的就应该是 $b(y)$，矛盾。故 $d(u_k)$ 的值已经是正确的了。

性质 2

假设计算完 $\text{Bundle}(u_k)$ 后，就出现了一个点 $u_l\in R$ 满足 $l>k>j\land d(u_l)

仿照 整点的处理 一节中的做法，根据 $\text{Ball}$ 的定义 $d(x,u_l)\ge d(x,u_k)$，而我们至多是用 $d(x)+d(x,u_l)$ 来松弛 $u_l$，那么必有 $d(u_l)\ge d(x)+d(x, u_k)\ge d(u_k)\ge d(u_j)$，与假设矛盾。于是性质 $2$ 总是成立。

性质 3

假设有一个点 $v\in\text{Bundle}(u_i)$，在计算完 $u_i$ 之后，我们维护的 $d^\prime(v)>d(v)$。

设 $s$ 到 $v$ 真正的最短路为 $p:s\rightarrow x\rightharpoonup y\rightarrow v$，其中 $x$ 是 $p$ 上最后一个满足 $x\in B_{i-1}$ 的点，那么就有 $d(y,b(y))\ge d(y,u_i)$。参考 散点的处理 一节，此时 $p$ 也可写成 $s\rightarrow x\rightharpoonup y\rightarrow z_1\rightharpoonup z_2\rightarrow v$ 的形式，$z_1,z_2$ 的含义和之前相同。（这里其实省略一些特殊情况，因为 $z_1,z_2$ 有可能就是 $x,y$）

在计算 $\text{Bundle}(u_i)$ 之前，$d(x)$ 就已经被正确地维护了，然后算法的步骤二中的 $z$ 会找到这条最短路上的 $z_1$，并给出正确的 $d(z_1)$，否则 $p$ 不会是最短路。

同时，$d(z_2,v)$ 在求解 $\text{Ball}$ 的过程中就被求出了，于是 $d(s,z_1)+w(z_1,z_2)+d(z_2,v)$ 会给出正确的 $d(v)$，矛盾。性质 $3$ 同样总是成立。

时间复杂度

易得，堆的复杂度为 $O(|R|\log n)=O(mp\log n)$。

然后预处理的复杂度为 $O(\frac mp\log\frac 1p)$。

$\text{Bundle Dijkstra}$ 中看上去枚举了很多点，但是因为 $\forall v\in V,|N(v)|\le 3$，于是每个 $\text{Ball}(v)$ 只会被枚举 $O(1)$ 次，总的复杂度就是 $O(\sum_{v\not\in R}|\text{Ball}(v)|)=O(\frac mp)$。

求导易知 $p=\sqrt{\frac{\log\log n}{\log n}}$ 时，总复杂度有最小值 $O(m\sqrt{\log n\log\log n})$。此时，在 $m=O(n)$ 的情形下，我们已经可以比普通的 $\text{Dijkstra}$ 算法优秀了。

非常数度图

可以看到之前的算法的瓶颈在于三度化之后有 $O(m)$ 个点，但是其实可以不要求一个点的度数为 $O(1)$，把约束放宽到 $\forall v\in V,\deg v\le k$，重新分析复杂度。

首先，我们还是要重新建图，此处复杂度为 $O(m)$，但是新图只会有 $O(\frac mk)$ 个点。

接着需要求解所有的 $\text{Ball}$ 和 $\text{Bundle}$，这里的堆中会有 $|S_v|k$ 个点，但是只会弹出堆顶 $|S_v|$ 次，使用合适的数据结构（比如 $\text{fib}$ 堆）可以做到 $O(\sum_{v\in V} |S_v|k+|S_v|\log(|S_v|k)=O(m+\frac mk\log m)$ 的复杂度。

然后对 $\text{Bundle}$ 间进行 $\text{Dijsktra}$，这里的复杂度是 $O(k\sum_{v\not\in R}|\text{Ball}(v)|)=O(\frac mp)$。

总的复杂度为 $O(m+\frac mk\log m+\frac mp)$，注意到在稀疏图中 $\log m=O(\log n)$，如果取

$$ \begin{align*} k=\frac mn\\ p= \begin{cases} \sqrt{\frac{\log\log n}{\log n}} &m\le n\log\log n\\ \sqrt{\frac{m}{n\log n}}&n\log\log n

可以得到复杂度为 $O(n\sqrt{\log n\log\log n})$ 和 $O(\sqrt{mn\log n})$，