近似最短路径 (5)

11.5 Agarwal-Godfrey 的 2 倍近似 Distance Oracle

Thorup-Zwick 当年在仿真图上面的想法，是选取许多丛集中心当作障碍物、以每个点为中心张出一颗气球，直到撞到任何一个障碍物为止。这样的概念可以应用在非常非常多的演算法中。如果暂时不关心构造出 Distance Oracle 的时间，只在乎「我们储存了多少东西」的话，可以发现，Throup-Zwick 的 3倍近似最短距离资料结构只需要 n^1.5 的储存空间。而事实上，存在某些很糟的图，如果要做到保证 3倍近似最短距离，真的必须要存 n^1.5-bits。类似地，如果是 2倍近似最短距离，那麽某些情形下真的得存到 n^2-bits 的储存空间。

在 2010 年，罗马尼亚出生 MIT毕业进入纽约 AT&T 实验室的 Mihai Pătrașcu (可惜 Pătrașcu 在 2012 年因为脑癌离世了，享年 29 岁，是非常非常年轻且厉害的理论电脑科学家) 与以色列巴伊兰大学教授 Liam Roditty 注意到，得用到 n^2-bits 储存空间的那些图，都必须是稠密图。他们以此设计出了一个期望 n^{4/3}m^{1/3}-个数字的资料结构。也就是说，当图相当稀疏(比方说，边数 m 不到 n^2) 的时候，需要的储存空间也少了很多。

当时在念伊利诺大学香槟分校 UIUC 的 Rachit Agarwal (现在是康乃尔大学的教授) 以及他的指导教授 Philip Brighten Godfrey (只花了三年就拿到柏克莱 PhD 了) 在 2013 年发表了一个比较简单的两倍近似最短距离资料结构 2-Stretch Distance Oracle。今天就来简单介绍这个资料结构存了哪些东西。

资料结构存什麽：

1. 先定义一个点集合 L，这个集合包含随机选取的 Õ(n/α) 个点，其中 α 是一个待定参数。
2. 对於所有图上的点 v，我们储存以下这些内容：
   • 到 L 之中任何一点的最短距离
   • 到 L 之中最接近的点 ℓ(v)、以及这个距离 r(v) (把所有小於这个距离的点定义为”气球” B(v))
3. 对於任何两个点 v 和 w，如果他们的气球 "相邻"、甚至有重叠：「B(v) 交集 B+(w) 非空」或是「B+(v) 交集 B(w) 非空」其中 B+(v) 的意思是气球及其往外扩张一条边碰到的那些点。这种情形发生的话，我们就用一个杂凑表纪录下 v 到 w 的距离 dist(v, w)。

如何查询最短路径：

1. 对於 u 和 v，如果 (u, v) 有被储存下来，就直接回传他们之间的最短距离。
2. 如果 (u, v) 没有被储存下来，那我们比较他们的气球半径大小 r(u) 和 r(v)：如果 r(u) < r(v)，那我们回传 dist(u, ℓ(u)) + dist(v, ℓ(u))；反之则回传 dist(u, ℓ(v)) + dist(v, ℓ(v))。

如此一来就可以在常数时间回传近似最短距离啦。有两个部分要证明：一个是如何正确选取 α 使得资料结构大小恰好是期望 n^{4/3}m^{1/3}。二是要证明回传的长度真的保证在 2倍最短距离之内。这两个部份的证明就请大家参考下面的短论文罗~

参考资料：

http://www.cs.cornell.edu/~ragarwal/pubs/stretch2.pdf