近似最短路径 (4)

11.4 Thorup-Zwick 的 Approximate Distance Oracle

什麽是 Distance Oracle 呢？这是一种资料结构，可以回答任两点之间的(近似)最短距离。举例来说，如果我们预先计算出任何两点之间的最短距离，储存在一个二维阵列里面，那麽这个二维阵列就是一个可以帮助我们在 O(1) 时间回答最短距离的一个 Distance Oracle。

当然，我们不一定要事先计算出任两点之间的最短距离并且储存起来。其中一个主要的原因是，如果 n 很大，那麽要储存 n^2 大小的表格可能相对就更大了。

在 Baswana-Sen 2003 年发表的 Graph Spanner 两年之前，丹麦电脑科学家 Mikkel Thorup (在美国纽约AT&T实验室待了15年以後，回到丹麦哥本哈根大学教授) 和以色列电脑科学家 Uri Zwick (现在是着名的以色列台拉维夫大学 Tel Aviv University 教授) 就已经在 2001 年发表了近似最短路径的 Distance Oracle。

Thorup-Zwick 的 Distance Oracle 是这样的，对於任何参数 k，它可以制作一个 k 层次的资料结构，使得能够在 O(k) 的时间内算出两个点 u 和 v 的近似最短路径，而它的误差不超过 2k-1 倍。
而这个 k 层次的资料结构，事实上是基於事先算好的某些点对的最短路径长度，并且把它是先储存起来。因为这些点对的最短距离是额外加上去的，可以把它看成是一个 graph emulator (仿真图)。

我们今天列举一个最简单的例子：k=2，这麽一来就可以跟昨天的 3倍近似最短路径的 Baswana-Sen Graph Spanner 做比较了。顺带一提，Baswana-Sen 也能够将它的构造方法推广到 k 层次、2k-1 倍的 Graph Spanner、而且也有描述如何利用 Thorup-Zwick 的方法在 Õ(kmn^{1/k}) 的时间构造出 k 层次的 Approximate Distance Oracle。

建构的方法如下：

1. 我们首先随机选取 sqrt(n) 个点形成集合 S。
2. 对 S 内所有点，计算其到所有图上的点的最短路径，并且将距离储存起来可供 O(1) 时间查询。这个最短路径可以在 |S| = O(sqrt(n)) 次 Dijkstra/BFS 的时间内做到。
3. 对於每一个剩下的点 u，我们从这个点做一个 “部分Dijkstra”：不断地拓展最接近的点集合直到碰到 S 内部的点就停下来。我们把这些距离通通储存起来，此外我们也记录下第一个碰到的 S 内点，并让 u 隶属於该内点的丛集。
4. 做完啦！

建构完毕以後，如果我们想知道 u 和 v 之间的近似最短距离：

1. 先查查看刚才有没有储存过的 dist(u, v)，如果有的话就直接回传。
2. 如果没有的话，看看 u 隶属於那一个丛集，假若它属於 Cu，那麽就回传 dist(Cu, v)。

这个方法时间是 O(sqrt(n) * m) 的，而查询只需要 O(1) 时间，就能保证找到的距离至多是 3倍原始距离啦！