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倍原始距離啦！