无权图全源最短路的快速算法

论文 On the All-pairs-shortest-path Problem. Raimund Seidel, 1992 阅读笔记。这篇文章给出了一个在 $O(M(n)\log n)$ 时间复杂度内计算出无向无权图全源最短路长度的算法，和一个在 $O(M(n)\log n)$ 时间复杂度内找出全源最短路的随机算法，其中 $M(n)$ 为对两个 $n\times n$ 的小整数矩阵做乘法的时间复杂度（注意：如果有 $M(n)=O(n^2)$，则找出全源最短路时间复杂度为 $O(n^2\log^2 n)$）。该算法还可以推广到有向无权图上。

计算全源最短路长度的算法

设 $G=\langle V,E\rangle$ 是一个顶点集合 $V=\{1,2,\ldots,n\}$ 的无向无权连通图（先讨论这种情况，剩下情况在最后一节补充），而 $A_{n\times n}$ 为 $G$ 的邻接矩阵。我们现在要计算 $d_{ij}\,(1\le i,j\le n)$ 表示编号为 $i,j$ 点之间的最短路长度。

命题 $1$：设矩阵 $Z=A^2$，对于任何 $1\le i,j\le n$，如果 $d_{ij}\le 2$，则 $z_{ij}>0$。

证明几乎显然。

然后让 $G'=\langle V,E'\rangle$ 为一张新图，而一条边 $(u,v)\in E'$ 当且仅当 $u\ne v$ 且 $d_{uv}\le 2$。可以发现 $(u,v)\in E'$ 当且仅当 $a_{ij}=1$ 或 $z_{ij}>0$。

再设 $t_{ij}$ 为在 $G'$ 中编号为 $i,j$ 点之间的最短路长度。

命题 $2$：对于任何 $1\le i,j\le n$：如果 $d_{ij}$ 为偶数，则 $d_{ij}=2t_{ij}$；如果 $d_{ij}$ 为奇数，则 $d_{ij}=2t_{ij}-1$。

证明：分两种情况讨论：

• 如果有：$d_{ij}=2s\,(s\in \mathbb N)$，则设在图 $G$ 中 $i,j$ 间最短路为 $v_0=i,v_1\ldots,v_{2s-1},v_{2s}=j$。则显然 $v_0=i,v_2,\ldots,v_{2s-2},v_{2s}=j$ 是图 $G'$ 中 $i,j$ 间的最短路，所以 $d_{ij}=2t_{ij}$。
• 如果有：$d_{ij}=2s-1\,(s\in \mathbb N^+)$，则设在图 $G$ 中 $i,j$ 间最短路为 $v_0=i,v_1\ldots,v_{2s-2},v_{2s-1}=j$。则显然 $v_0=i,v_2,\ldots,v_{2s-2},v_{2s-1}=j$ 是图 $G'$ 中 $i,j$ 间的最短路，所以 $d_{ij}=2t_{ij}-1$。

得证。$\Box$

设 $\delta(G)$ 为图 $G$ 的直径（两点间最短路长度的最大值），由命题 $2$ 可可知：将图 $G$ 上的问题转化为图 $G'$ 上的问题，直径大致减半，更具体的有：$\delta(G')=\lceil \delta(G)/2\rceil$。这也是这个算法减小问题规模的关键。

现在的最主要问题变为判断 $d_{ij}$ 的奇偶性，如果这一问题得以解决，就可以不断递归到直径更小的问题上，最后直径不超过 $2$ 的时候结束递归。

为解决这一问题我们先给出一个极其显然的定理：

命题 $3$：设 $1\le i,j\le n$ 且 $i\ne j$。则对于在图 $G$ 与点 $j$ 有连边的点 $k$，都有：$d_{ij}-1\le d_{ik}\le d_{ij}+1$，并且一定存在一个 $k$ 使得 $d_{ik}=d_{ij}-1$。

这个即是最短路的三角不等式在无向无权图上的直接运用。

命题 $4$：设 $1\le i,j\le n$ 且 $i\ne j$。则如果有 $d_{ij}$ 为偶数，则对于任何在 $G$ 中与点 $j$ 有连边的点 $k$ 都有 $t_{ik}\ge t_{ij}$；如果有 $d_{ij}$ 为奇数，则对于任何在 $G$ 中与点 $j$ 有连边的点 $k$ 都有 $t_{ik}\le t_{ij}$，并且一定会有一个 $k$ 使得 $t_{ik}<t_{ij}$。

证明：分两类情况讨论：

• 若 $d_{ij}=2s\,(s\in \mathbb N)$，则有命题 $3$ 可得对于任何在 $G$ 中与点 $j$ 有连边的点 $k$ 都有 $d_{ik}\ge 2s-1$，那么再由命题 $2$ 可推出 $t_{ik}\ge s=t_{ij}$。
• 若 $d_{ij}=2s-1\,(s\in \mathbb N^+)$，则有命题 $3$ 可得对于任何在 $G$ 中与点 $j$ 有连边的点 $k$ 都有 $d_{ik}\le s-1$，并且一定存在一个 $k$ 使得 $d_{ik}=2s-2$，那么再由命题 $2$ 可推出另一半结论。

得证。$\Box$

作为命题 $4$ 的直接推论，我们得到命题 $5$：

命题 $5$：对于任何 $1\le i,j\le n$：$d_{ij}$ 为偶数当且仅当 $\sum\limits_{(k,j)\in E}t_{ik}\ge t_{ij}\cdot \text{deg}_G(j)$；$d_{ij}$ 为奇数当且仅当 $\sum\limits_{(k,j)\in E}t_{ik}< t_{ij}\cdot \text{deg}_G(j)$，其中 $\text{deg}_G(v)$ 表述在图 $G$ 中点 $u$ 的度数。

证明便是反证然后导出与命题 $4$ 间的矛盾。

注意到 $\sum\limits_{(k,j)\in E}t_{ik}=\sum\limits_{k=1}^nt_{ik}a_{kj}$，于是我们定义矩阵 $X=TA$，则判断 $d_{ij}$ 的奇偶性可以变为判断 $x_{ij}$ 与 $t_{ij}\cdot\text{deg}_G(j)$ 的大小关系。

这样我们就可以得到算法的伪代码：

伪代码第 $9$ 行的 $\text{deg}_A(v)$ 表示邻接矩阵为 $A$ 的图（不计重边则是唯一的）中 $v$ 的度数。

设 $T(n,\delta)$ 为对一个有 $n$ 个点且直径为 $\delta$ 的图执行如上算法的时间复杂度，则有：

$T(n,\delta)= \begin{cases} M(n)+O(n^2) & \delta\le 2 \\ T(n,\lceil \delta/2\rceil)+2M(n)+O(n^2) & \delta>2 \end{cases}$

易得：

$T(n,\delta)=(2\lceil\log_2\delta\rceil-1)M(n)+O(n^2\log \delta)=O(M(n)\log n)$

上述推导用到了 $\delta=O(n)$ 与 $M(n)=\Omega(n^2)$，其中 $M(n)$ 为对两个 $n\times n$ 的小整数矩阵做乘法的时间复杂度，有 $M(n)=O(n^{2.376})$。

找到全源最短路的随机算法

注意这里的「找到」指的不是对每一对 $i,j$ 都输出从 $i$ 到 $j$ 上最短路的每一个点。因为如果这样这个问题不可能在 $o(n^3)$ 内解决（$\Theta(n^2)$ 对点，每对点间距离为 $O(n)$）。

这个算法「找到」的是「后继矩阵」$S_{n\times n}$，对于每个 $i\ne j$，$s_{ij}$ 的值表示与 $i$ 相邻且在 $i$ 到 $j$ 最短路上的点的编号，如果有多个这样的点任取一个。显然这样的「后继矩阵」可以更高效的表示全源最短路。

我们来定义一个新的 $01$ 矩阵乘法 $\circ$（原文叫 the boolean product witness matrix，原谅我不会翻译）。有两个 $01$ 矩阵 $A,B$，则我们定义 $W=A\circ B$ 满足如下条件：

$w_{ij}= \begin{cases} \text{some }k\text{ such that } a_{ik}=1\text{ and }b_{kj}=1\text{, and} \\ 0\text{ if no such }k\text{ exists.} \end{cases}$

这里的 some 表示了如果有多个这样的 $k$ 任取一个的意思。对于满足 $a_{ik}=b_{kj}=1$ 的 $k$，我们称 $k$ 是 $(i,j)$ 的一个 witness。

现在我们先使用上一节的算法求得了全源最短路的长度，并将 $d_{ij}$ 存在矩阵 $D_{n\times n}$ 里面。那么显然 $s_{ij}=k$ 等价于 $d_{kj}=d_{ij}-1$ 且 $a_{ik}=1$。

那么我们可以将 $S$ 表示为如下形式：

$s_{ij}=(A\circ Q^{(l)})_{ij},\text{ with }l=d_{ij}$

其中 $q^{(l)}_{ij}=[d_{ij}=l-1]$。

要计算 $n-1$ 个 $\circ$ 显然太慢了。这里有一个 key observation 就是说由命题 $3$ 可得：$d_{ij}-1\le d_{kj}\le d_{ij}+1$，于是你发现其实 $s_{ij}=k$ 等价于 $a_{ik}=1$ 且 $d_{kj}\equiv d_{ij}-1\pmod 3$。也就是说 $d$ 都可以模一个 $3$，所以我们改写一下 $Q^{(l)}$ 的定义：$q^{(l)}_{ij}=[d_{ij}\equiv l-1\pmod 3]$，上面的表示只剩下三项：

$s_{ij}=(A\circ Q^{(l)})_{ij},\text{ with }l=d_{ij}\bmod 3$

接下来先给一个整个算法的伪代码，然后再进行分析：

我们先 $\text{BPWM}$ 函数进行时间复杂度分析。对于伪代码第 $3$ 到 $10$ 行的循环，设 $M(n)=O(n^\omega)$，则将 $n\times d$ 与 $d\times n$ 两个矩阵相乘的时间复杂度为 $O(n^2d^{\omega-2})$。所以这个循环时间复杂度表达式如下：

$p\sum_{l=0}^{\lceil \log_2 n \rceil -1}\Big(O(n^2)+O(n^2(2^l)^{\omega-2}) \Big)= \begin{cases} O(p\cdot n^\omega) & \omega>2 \\ O(p\cdot n^2\log n) & \omega=2 \end{cases}$

接下来我们将分析如何选取 $p$ 使得伪代码第 $11$ 到 $13$ 行的循环期望时间为 $O(n^2)$。更具体的，我们分析对于任何 $(i,j)$，其存在一个 witness，但是在第一个循环中没有找到的概率至多为 $1/n$。

命题 $6$：对于 $\text{BPWM}$ 第一个循环（伪代码第 $3$ 到 $10$ 行）与任意的数对 $(i,j)$，如果 $k_1,k_2,\ldots,k_d$ 中恰有一个是 $(i,j)$ 的 witness，不妨设为 $k_\nu$，则 $c_{ij}=k_\nu$。

证明：因为只有 $k_\nu$ 满足 $a_{ik_\nu}=b_{k_\nu j}=1$，故 $c_{ij}=\sum\limits_{r=1}^d k_ra_{ik_r}b_{k_r j}=k_\nu$。$\Box$

对于任意数对 $(i,j)$，如果其没有 witness，则在执行完伪代码第 $2$ 后 $w_{ij}$ 便是 $0$，之后 $w_{ij}<0$ 的条件也一直不会被触发，无需考虑。

否则如果 $(i,j)$ 有 witness，且一共有 $c\,(c>0)$ 个 witness。假设有一次过程中 $d$ 满足 $n/2\le cd\le n$（因为 $d$ 取遍所有不超过 $n$ 的 $2$ 的次幂，所以这样的 $d$ 一定存在），下面这个命题指出，「$k_1,k_2,\ldots,k_d$ 中恰有一个 witness」这个事件为假的概率不超过 $1-\dfrac 1{2\text{e}}$，其中 $\text{e}$ 是自然对数的底数。又因为只要有「$k_1,k_2,\ldots,k_d$ 中恰有一个 witness」成立，则 $(i,j)$ 的 witness 便被找到，所以经过循环后 $(i,j)$ 的 witness 没被找到的概率也不超过 $1-\dfrac 1{2\text e}$。

命题 $7$：一个袋子里有 $n$ 个球，其中有 $c\,(c\le n)$ 个红球，剩下是蓝球。进行 $d$ 次抽取放回过程，其中 $d$ 满足 $n/2\le cd\le n$，假设每次抽取抽到每个球的概率都是 $1/n$。则这 $d$ 次恰有一次抽出红球的概率至少是 $\dfrac 1{2\text{e}}$。

证明：这个事件概率的表达式显然是：

$d\cdot \dfrac cn\left(1-\dfrac cn\right)^{d-1}$

又因为 $n/2\le cd\le n$，所以有：$\dfrac{dc}n\ge \dfrac 12$ 与 $\dfrac cn\le \dfrac 1d$。所以将上式进行放缩：

$d\cdot \dfrac cn\left(1-\dfrac cn\right)^{d-1}\ge \dfrac 12\left(1-\dfrac 1d\right)^{d-1}>\dfrac 1{2\text{e}}$

得证。$\Box$

我们又将关于 $d$ 的循环重复了 $p$ 遍，令 $\left(1-\dfrac 1{2\text e} \right)^p\le \dfrac 1n$ 得 $p$ 的最小值为 $-\ln n/\ln\left(1-\frac 1{2\text e}\right)$，是 $O(\log n)$ 级别的。

故可写出最后的时间复杂度表达式：

$\begin{cases} O(n^\omega \log n) & \omega>2 \\ O(n^2\log^2 n) & \omega=2 \end{cases}$

补充

$G$ 不连通这个算法仍适用，只是如果 $(i,j)$ 间没有路径，则 $d_{ij}=0$。那么判断一下如果 $i\ne j$ 且 $d_{ij}=0$，那么 $(i,j)$ 间的路径一定不存在。

$G$ 是有向图也是适用的，我们只需要把 $\text{Work}$ 函数的伪代码中，第九行 $\text{deg}_A(v)$ 的含义由度数改为入度即可。

这个算法实践中并不快，一是因为快速的矩阵乘法常数大，二是递归时的开销不小。

参考文献

[1] On the All-pairs-shortest-path Problem. Raimund Seidel, 1992.