最短路径问题 (7)

10.9 Chan’s APSP 演算法

我们今天来介绍一个 O(n^3 / log n) 时间复杂度的 APSP 演算法。

切成条状的 (min, +)-矩阵乘法

Fredman 在 1976 年观察到一些有趣的性质。
对於两个矩阵 A 和 B 来说，我们可以把 A 切成直条 [A1, A2, …, Aq]、把 B 切成横条 [B1; B2; …; Bq]，然後把计算 A⋆B 的工作变成计算 min{ A1⋆B1, A2⋆B2, …, Aq⋆Bq }。换句话说，只要计算 q=(n/d) 个大小为 n * d 和 d * n 的 (min, +)-矩阵相乘，最後再合并起来就行了。

如果我们能将这个长条状的矩阵乘法加速(通常需要 n^2 * d 的时间) 到 n^2，我们就能加快 d 倍了！

计算 APSP 的时间和做 (min, +)-矩阵乘法差不多

我们要计算距离矩阵 D，可以透过利用 (min, +)-矩阵乘法对相邻矩阵重复平方 log n 次，来找出任两点之间的最短距离。如果计算 (min, +)-矩阵相乘需要 M(n)，那总时间复杂度就是 O(M(n) log n)。在 Aho, Hopcraft, 和 Ullman 於 1987 年撰写的演算法教科书中，他们展示了一种方法，只要把 (min, +)-矩阵相乘当成黑盒子，就可以在 O(M(n)) 的时间内算出 APSP，不需要额外多一个 log n。

把上面两个想法合并起来

这篇文章介绍 Timothy Chan 在 2008 年提出利用 「d维向量的支配集」的概念，在 O(n^2 + c^d n^1.38) 做出 n * d 和 d * n 矩阵以 (min, +) 相乘後的结果 (c 是某个常数)。若我们选取 d = log n / log c = O(log n)，那麽我们就得到一个总时间为 O(n^3 / d) = O(n^3 / log n) 的演算法啦！