10.10 Thorup’s 無向非負整數權重 SSSP 演算法

今天來介紹 Thorup 在 1997 年發表的整數模型線性時間的 SSSP 演算法。
(可能會跳過很多細節所以最終仍然沒辦法完整地呈現演算法的全貌)

我們知道 Dijkstra 1959 年推出的演算法在如 Fibonacci Heaps 等特殊堆積的情況下可以做到 O(m + n log n) 的執行時間，在圖上總邊數是稀疏的時候仍然不是線性的。而在之後的數十年間也有很多相關的文章引入不同的堆積想辦法加速。Thorup 的演算法也不例外。

不過呢，Thorup 的演算法必須要在無向圖而且是非負整數的情形下才能做到線性時間。(而且還要用到假設整數乘法可以在常數時間做到這個條件)。需要整數乘法的原因是某些底層的資料結構需要取出最高有效位元 most significant bit。

演算法大方向有三：首先，利用一個對 Dijkstra 演算法的小觀察，得到「不一定要按照最短距離長度逐一考慮點」的概念。接著，因為不一定要按照最短距離長度排序，只要足夠接近最短距離就可以保證該點當前的距離是最小的；因此我們可以將所有儲存的距離直接敲去末端的一些位數，並且對這個模糊的距離使用桶子排序。最後使用遞迴方法將點集分拆成若干子集合，使得橫跨不同子集合之間的邊權重都超過某個數值。這樣的分拆方法可以建構出一個階層樹 (component hierarchy)：若兩個葉子位於第 i 層(樹葉為 0) 的祖先不同，那麼這兩個葉子對應到原圖上的點距離至少為 2^i。換句話說，在第 i 層的資料結構其存儲的最短距離們都可以敲去 i 個 bit。為什麼會需要無向圖呢？因為在資料結構更新的過程，某個階層內個某個點集合中的某個點若被移除，該點集合會根據新的最短距離(這個代表集合的最短距離會越來越大) 重新放到某個桶子排序的桶子裡。無向圖的好處是，這個新的桶子位置，只會比舊的桶子位置至多移動一點點。

建構階層樹會用到「利用 MSB 的最小生成樹」以及「Atomic Heaps」。論文中也有描述到，若不使用常數異常驚人的 (2^12^20) Atomic Heaps，採用常見的 disjoint set 計算最小生成樹的話，可以做到 O(mα(n)) 的時間，也是幾乎線性了。

參考資料：
http://forskning.diku.dk/PATH05/Thorup-1.pdf
https://dl.acm.org/doi/10.1145/316542.316548
http://courses.csail.mit.edu/6.854/20/sample-projects/A/connection%20_between_SSSP.pdf