近似最短路径 (2)

11.2 距离不超过 3 倍的 Baswana-Sen Spanner

如果我们把近似最短距离的要求再度放宽，比方说找出一个子图 H，使得图 H 上任两点之间的最短距离，都不超过图 G 的 3 倍。在印度理工学院念博士班的 Surender Baswana 与他的指导教授 Sandeep Sen 发表了一篇非常有效率的演算法，在线性时间内找出一个子图 H 满足上述条件，而且这个子图的边数至多只有期望 n^1.5 条（在最坏情况下达到理论下界），跟前一节提及的 +2 Spanner 数量相近。

要怎麽做呢？演算法如下：

1. 首先让每个点以 1/n^{0.5} 的机率被选入集合 S 作为丛集中心(Cluster Center)。
2. 对於所有没被选中的点 v，如果他与其中一个 S 的点 x 相邻，就把 v 指派给 x。如果与多个 S 内的点相邻，就随意挑选一个 S 中的点 x 来指派，并且将 (v, x) 这条边加入 H。经过这步骤以後，绝大部分的点都已经被指派进入某个丛集了。
3. 如果一个点没有被指派给任何丛集(也就是说它不与所有 S 内的点相邻)，就把它所有的相邻边都加入 H。
4. 对於每个点 v (无论有或没有选中)，我们将它的邻居们根据丛集分门别类，对於每个相邻的丛集，挑选一条边加入 H。
5. 然後我们就做完啦！

时间复杂度是线性的：每一个步骤，都会让每个点、每条边被考虑至多 2 次(边有两个方向)。
图 H 内的期望边数有 n^1.5 条，因为首先，集合 S 的大小是期望 n^0.5 个点。因此，第四步骤所加入 H 的边数是期望 n * n^0.5 = n^1.5 条。然後，第二步骤增加的边数为 O(n)。接着，如果一个点没有被指派进入任何一个丛集，那麽它的期望邻居数量是 n^0.5 个点，所以第三步骤期望加入的总边数也是 n^1.5 条。

最後，需要稍微感觉一下为什麽这个演算法保证了至多 3 倍。事实上，如果这是一个无向无权图，那麽距离其实是 “2倍+1”。如果是有权重的图，我们可以修改第二步骤(指派给最接近的点)、以及第四步骤(每个丛集选最接近的那个邻居加边)，这样能保证 “3倍”。

考虑一条没有被加入 H 的边 (u, v)，显然 u 和 v 都属於某个丛集(否则这条边就会被第三步骤抓住)。不妨假设 v 的丛集中心是 Cv。那根据第四步骤，在我们考虑 u 的时候，必定连了一条 u → Cv 所在丛集的某个点 w (而此时 w 必定不是 v)。於是，我们有一条路 u → w → Cv → v，距离保证是至多 3 倍。

考虑任何一条图 G 上的最短路径 s ⇝ t，这条路径上在图 H 所有缺失的边都能以上述方法在 3 条边之内搞定。因此这个图 H 的确是近似最短路径的 3-Spanner。

值得注意的是，这个演算法并没有办法帮助我们快速地找出近似 APSP。若要对每一个点都做一次 BFS/Dijkstra，那麽时间复杂度仍然是期望的 n^2.5。