近似最短路径 (6)

11.6 距离标签 Distance Labellings

最短距离资料结构 Distance Oracles 有一个非常极端的形式，那就是距离标签：透过预处理，给予图上的每一个点 v 一个二元字串 L(v)，作为标签 (labels)。这个标签可以储存任何的讯息。但是，当我们想要知道某两个点 u 和 v 之间的最短距离的时候，只能依靠 L(u) 和 L(v) 这两个标签的资讯，就必须要推算出最短距离。

昨天说明的 Agarwal-Godfrey Distance Oracle 满足上述 (Approximate) Distance Labeling 的条件：对於每个节点，我们只要在标签写下与之有关的所有距离即可。查询的时候由於已经从标签上得知 dist(u, ℓ(u))、 dist(v, ℓ(u))、 dist(u, ℓ(v))、 dist(v, ℓ(v)) 这几个数值，可以直接算出近似距离。

这个距离标签有什麽好处呢？最直接的好处就是，经过预处理以後，我们不需要记住整张图、甚至在查询的时候也只需要存取两张标签，对於常见资料库的存取负担是极小的。

以色列魏茨曼科学研究学院的教授 David Peleg 在 1999 年提出了 Distance Labelling 的概念。
在 Peleg 提出的论文 中利用了树覆盖的概念，来得出 O(log n)-近似距离标签。我们今天会先介绍大方向，然後明天继续把细节补完：

对於每一个点 v，我们将它的「距离 L 以内」的 BFS 树刻划出来。选取 L=1, 2, 4, 8, ...，我们就会得到 log n 棵树。总共有 n log n 棵，每一层 L 有 n 棵 BFS 树。对於每一层距离 L，同一个点可能出现在多棵 BFS 树里面。如果我们可以把这些树稍加合并，使得每一个点只出现在至多 O(log n) 棵树上，而且同时不牺牲太多距离 (原本对於某一层 L，树上任意两点的距离不超过 2L，但是合并一些树以後，树上任何两点的距离可能会超过 2L)。在我们的例子中，这个距离会被牺牲 log n倍。

这麽一来，我们能对每一个节点定义他的距离标签，这个标签大小是 O(log^3 n)-bits 的：
有 log n 个不同的 L 数值
每一个不同的 L，我们记录下这个点出现所在的 "被合并过的BFS树" 的编号，对於一个固定的 L，最多有 O(log n) 个不同的编号，因为出现在至多 O(log n) 棵树上。
每一棵树的编号是一个 O(log n)-bits 的整数，因为合并前至多只有 n log n 棵树，因此合并後也只有这麽多，我们可以将他们重新编号。

要怎麽估计 u 和 v 的最短距离呢？很简单，把它们的距离标签拿出来看看：对於每一层 L，检查他们所出现的那些树的编号。如果 u 和 v 出现在同一棵树上，代表他们距离不超过 (log n)L。如果 u 和 v 没有出现在同一棵树，那麽代表他们的最短距离一定超过 L。

剩下什麽细节呢？剩下把 BFS 树合并的方法。方法单纯，而且与气球的概念非常类似。这个我们明天继续~