¶ 问题描述

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

¶ 思路

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

¶ 随机选点

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

假设每个点被选中的概率为，那么一个度数为d的点的邻居中，有一个点被选中的概率就是。可以证明只要随机选出个点即可（我不会证明）。其中表示，其中为常数。

¶ 两层图：

设为度数的点的集合。我们随机选出个点，使得所有中的点高概率与中的某个点相邻。

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

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

注意到w高概率与中的某个点w'相邻，所以考虑用w'为跳板，求出u到w'和w'到v的最短距离。记原图中u和v之间的最短距离为，那么，，所以，即误差最大为2。

所以我们先在原图中对每个中的点跑一遍BFS，拿到里每个点对的最短距离，这个时间复杂度为。然后往中加入权重为的从u到v的边，其中，，加入的这些边的集合记为，得到的图则为，其边数仍然为。然后对得到的图的每个点跑dijkstra，复杂度，就能得到误差最多为2的每个点对之间的最短路长度了。总的复杂度就是。

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

¶ 三层图：

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

令为度数的点构成的点集。
令为度数的点构成的点集。
令为随机选出的个点，这样里每个点都大概率与一个中的点相邻。
令为随机选出的个点，这样里每个点都大概率与一个中的点相邻。
令为满足或的边(u, v)构成的边集。
令为满足或的边(u, v)构成的边集。
令为将每个中的点连接到一个中的点的边构成的集合。注意，每个中的点对应中的一条边，不然最后的复杂度就不对了。

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

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

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

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

所以总的流程如下：

1. 在原图对每个中的点跑BFS，得到边集，复杂度。
2. 在中对每个中的点跑BFS，得到边集，由于，，所以复杂度。
3. 对每个点u，在中对每个点跑dijkstra。由于，，，，所以总的边数是，复杂度是。

所以最终的复杂度就是。一切都刚刚好，太妙了orz

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

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

令为度数的点构成的集合。就是所有点的集合。
令为随机选出的个点，这样每个中的点都大概率跟某个中的点相邻。。
令为满足或的边(u, v)构成的边集。
令为将每个中的点连接到一个中的点的边构成的集合。

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

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

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

因为，，，所以跑dijkstra的总边数为，由于，所以复杂度为。跑k次，总复杂度。

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

¶ 对稀疏图进行优化

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

对k层图使用这个优化后，为度数的点构成的集合，，，。

我们假设，那么，跑一层的复杂度是，跑k层，复杂度就是。由于，所以这个复杂度永远不会比之前的更差。

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

oooooooooooooooooooooooorz