最短路径问题 (8)

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