¶ 问题描述

给定一个n个点m条边的无向无权重的图，找出所有点对之间的近似最短距离。

¶ 思路

最简单的方法就是从每个点开始跑BFS了。BFS的时间复杂度是O(m)的，那么总的时间复杂度就是O(nm)的。但是如果是稠密图，那O(m) = O(n²)，总的时间复杂度就是O(n³)了。所以思路就是生成边数比较少的子图，然后加上一些构造出来的边来弥补那些被删掉的边造成的影响，再对得到的图跑最短路，来近似给出完整的图的结果。

¶ 随机选点

生成边数比较少的子图时，常用的方法是在图中随机选一些点，使得度数 ≥ d的点大概率与某个选出来的点相邻。

假设每个点被选中的概率为1/k，那么一个度数为d的点的邻居中，有一个点被选中的概率就是1 − (1−1/k)^d。可以证明只要随机选出Õ(n/d)个点即可（我不会证明）。其中Õ(n)表示O(n log^c(n))，其中c为常数。

¶ 两层图：Õ(n^5/2)

设V₁为度数 ≥ n^1/2的点的集合。我们随机选出Õ(n^1/2)个点D₁，使得所有V₁中的点高概率与D₁中的某个点相邻。

令E₂为满足u ∉ V₁或v ∉ V₁的边(u, v)组成的边集。这样E₂就相当于我们生成的边数比较少的子图了。由于其中的每条边的两个端点中，其中一方的度数必小于n^1/2，也就是说，我们遍历所有的度数n^1/2的点发出的边，即可遍历到所有的边，然后这样的点的个数最多是n，所以总的边数|E₂| ≤ n ⋅ n^1/2 = n^3/2。

我们在这个子图里对每个点跑BFS的话，对于点对(u, v)，假如u和v以及它们的最短路径上所有的点的度数都小于n^1/2，那么就可以求出来。但是如果路径上存在某个度数 ≥ n^1/2的点w（有可能是u或v本身），使得最短路径上某条边可能不在E₂里，我们怎么估计出原图中u和v的最短路呢？

注意到w高概率与D₁中的某个点w’相邻，所以考虑用w’为跳板，求出u到w’和w’到v的最短距离。记原图中u和v之间的最短距离为δ(u,v)，那么δ(u,w′) ≤ δ(u,w) + 1，δ(w′,v) ≤ δ(w,v) + 1，所以δ(u,v) = δ(u,w) + δ(w,v) ≤ δ(u,w′) + δ(w′,v) + 2，即误差最大为2。

所以我们先在原图中对每个D₁中的点跑一遍BFS，拿到D₁ × V里每个点对的最短距离，这个时间复杂度为Õ(n^1/2⋅m) = Õ(n^5/2)。然后往E₁中加入权重为δ(u,v)的从u到v的边，其中u ∈ D₁，v ∈ V，加入的这些边的集合记为δ(D₁×V)，得到的图则为E₁ ∪ δ(D₁×V)，其边数仍然为O(n^3/2)。然后对得到的图的每个点跑dijkstra，复杂度Õ(n^5/2)，就能得到误差最多为2的每个点对之间的最短路长度了。总的复杂度就是Õ(n^5/2)。

一些想法：上面的描述中，使用E₂时，我其实加上了u和v的度数都小于n^1/2的假设，这样其实E₂里只保留两个端点的度数都小于n^1/2的边就好了，然而这样并不能减少E₂里的边数，而且这样的话，对于相邻的一个度数小于n^1/2，一个度数 ≥ n^1/2的点，本来可以都在E₂里求出精确值，但是却非得以D₁中的点为跳板，导致可能出现误差。

¶ 三层图：Õ(n^7/3)

三层图的结构即一个原图，一个2/3的子图，一个1/3的子图，而且由于同样只用了一个中继点，最大的误差仍然为2。

令V₁为度数 ≥ n^2/3的点构成的点集。
令V₂为度数 ≥ n^1/3的点构成的点集。
令D₁为随机选出的Õ(n^1/3)个点，这样V₁里每个点都大概率与一个D₁中的点相邻。
令D₂为随机选出的Õ(n^2/3)个点，这样V₂里每个点都大概率与一个D₂中的点相邻。
令E₂为满足u ∉ V₁或v ∉ V₁的边(u, v)构成的边集。
令E₃为满足u ∉ V₂或v ∉ V₂的边(u, v)构成的边集。
令E^*为将每个V₂中的点连接到一个D₂中的点的边构成的集合。注意，每个V₂中的点对应E^*中的一条边，不然最后的复杂度就不对了。

我们先从E₃开始考虑。如果我们直接在E₃上对每个点做BFS，那假如点对(u, v)之间的最短路上所有点（包括u和v）都不属于V₂，那么求出来的就是精确值。但是，如果路径上存在属于V₂的点，那么就可能有边不在E₃中。这时我们考虑引入中继点来弥补。假设w是最后一个属于V₂的点（可能是v），那么在D₂中就大概率有一个点w’与w相邻。显然w到v的最短路径上的边都在E₃里，因此w’到v在E₃ ∪ E^*上的最短路径长度最多比w到v的最短路径大1。现在问题转化为如何得到u到w’的无误差最短路长度，即每个D₂ × V中的点对的最短路径长度。

最简单的方法当然是直接在原图上对每个D₂中的点跑BFS，但是这样的话复杂度太高了。

其实对于三层的图，有一个很美妙的性质：如果u到v的最短路上存在属于V₁的点w，那么大概率存在一个D₁中的点w’，使得w’与w相邻，然后只要我们先对每个D₁中的点跑BFS，得到边集δ(D₁×V)，然后只要图中加入这个边集，就能得到这种情况下误差最大为2的最短路长度，跟两层图同理。

这样，我们就只需要求解对于D₂ × V中的点对，两点之间的最短路径上所有点都 ∉ V₁时，最短路径是多少了。我们发现，这些边恰好都在E₂中。所以我们在E₂里对每个D₂中的点跑BFS，得到δ_E2(D₂×V)。算起点为u的最短路径时，只需要把δ_E2({u}×D₂)加入到图中即可，不然复杂度不对。

所以总的流程如下：

1. 在原图对每个D₁中的点跑BFS，得到边集δ(D₁×V)，复杂度Õ(n^7/3)。
2. 在E₂中对每个D₂中的点跑BFS，得到边集δ_E2(D₂×V)，由于|D₂| = Õ(n^2/3)，|E₂| = O(n^5/3)，所以复杂度Õ(n^7/3)。
3. 对每个点u，在E₃ ∪ E^* ∪ δ(D₁×V) ∪ δ_E2({u}×D₂))中对每个点跑dijkstra。由于|E₃| = O(n^4/3)，|E^*| = O(n)，|δ(D₁×V)| = Õ(n^4/3)，|δ_E2({u}×D₂))| = Õ(n^2/3)，所以总的边数是Õ(n^4/3)，复杂度是Õ(n^7/3)。

所以最终的复杂度就是Õ(n^7/3)。一切都刚刚好，太妙了orz

¶ 推广到多层：Õ(kn^2 + 1/k)，误差最大为2(k-1)。

分为k层，共k-1个中继节点，所以误差最大为2(k-1)。

令V_i为度数 ≥ n^{1 − i/k}的点构成的集合。V_k就是所有点的集合V。
令D_i为随机选出的Õ(n^i/k)个点，这样每个V_i中的点都大概率跟某个D_i中的点相邻。D_k = V。
令E_i为满足u ∉ V_i − 1或v ∉ V_i − 1的边(u, v)构成的边集。
令E_i^*为将每个V_i中的点连接到一个D_i中的点的边构成的集合。

思路：从i = 1到k，每次求出D_i × V中每个点对的误差为2(i-1)的最短路径长度，算完到i = k后，就把V × V中每个点对的误差为2(k-1)的最短路径长度给算出来了，这就是我们要求的。

i = 1的情况，直接在原图上（即E₁）对每个D₁中的点做BFS即可。

i > 1的情况，假如我们在E_i中对每个D_i中的点跑BFS，那么对于点对(u, v)，假如最短路径上所有点都 ∉ V_i − 1，那么求出的就是精确值，否则，设w为最后一个属于V_i − 1的点，那么大概率存在一个w′ ∈ D_i − 1，使得w’与w相邻。从w’到v的最短路径长度可以在E_i ∪ E_i − 1^*中求出来。然后我们又已知D_i − 1 × V中每个点对的误差为2(i-2)的最短路径长度，假设u到D_i − 1的最短路径长度构成的边集是δ′({u}×D_i − 1)，那么对每个u ∈ D_i，以u为起点，在E_i ∪ E_i − 1^* ∪ δ′({u}×D_i − 1)里跑dijkstra即可得到误差最多为2(i-1)的最短路径长度。

因为|E_i| = O(n^{2 − (i−1)/k})，|E_i − 1^*| = O(n)，|δ′({u}×D_i − 1)| = Õ(n^(i−1)/k)，所以跑dijkstra的总边数为Õ(n^{2 − (i−1)/k})，由于|D_i| = Õ(n^i/k)，所以复杂度为Õ(n^2 + 1/k)。跑k次，总复杂度kÕ(n^2 + 1/k)。

我的想法：可不可以把三层图里直接把最顶层消掉的方法泛化到这里呢？少一个中继点就可以提高一些精度。

¶ 对稀疏图进行优化

注意到，前面的算法在分层的时候只用到了n，但是如果是稀疏图的话，其实高度数的节点是很少的，那其实很多层其实是白分了。所以对稀疏图的优化的思路就是在分层的时候，我们同时用到n和m。论文里给出的分层方法是把原先的n^{1 − i/k}改成(m/n)^{1 − i/k}。

对k层图使用这个优化后，V_i为度数 ≥ (m/n)^{1 − i/k}的点构成的集合，|D_i| = Õ(n/(m/n)^{1 − i/k}) = Õ(n^{2 − i/k}/m^{1 − i/k})，|E_i| = O((m/n)^{1 − (i−1)/k}⋅n) = O(m^{1 − (i−1)/k}n^(i−1)/k)，|δ′({u}×D_i − 1)| = Õ(n^(i−1)/k/m^{1 − (i−1)/k})。

我们假设O(m) ≥ O(n)，那么|E_i∪E_i − 1^*∪δ′({u}×D_i − 1)| = Õ(m^{1 − (i−1)/k}n^(i−1)/k)，跑一层的复杂度是|D_i||E_i| = Õ(n^{2 − 1/k}m^1/k)，跑k层，复杂度就是Õ(kn^{2 − 1/k}m^1/k)。由于O(m) ≤ O(n²)，所以这个复杂度永远不会比之前的kÕ(n^2 + 1/k)更差。

论文：<www.cs.tau.ac.il/~zwick/papers/apasp.ps.gz>

oooooooooooooooooooooooorz