最短路径问题 (4)

10.5 Seidel’s APSP 演算法

如果一个无向图的所有边都没有权重，那麽就能用奥地利出生、从康乃尔大学念完博士毕业回到德国教书的 Raimund Seidel 教授提出的演算法，巧妙利用普通的矩阵相乘加上倍增的概念计算出任两点的最短距离。

Seidel 从一个很简单的子问题着手进行：想像一下，如果一张图是完全图，那麽显然任意点对距离都是 1，能轻易求得最短距离矩阵。那麽，如果这张图不是完全图，但是「把相邻矩阵平方後却得到完全图」的话，我们也能轻易求得最短距离矩阵：没有边的点对距离一定是 2、有边的点对距离一定是 1。

现在退而求其次，假设我们根据图 G 的相邻矩阵 A(G)，平方後，将非零的位置留下来，得到平方图 G^2 的相邻矩阵 A(G^2)。接着将 A(G^2) 送入演算法，并且求得任两点之间的最短距离 D(G^2)。Seidel 的决定性观察，可以帮助我们从 D(G^2) 还原出 D(G)。

换句话说，我们想要找的就是根据 u 和 v 在 G^2 之中的最短距离 D(G^2)[u, v]、搭配已知的相邻矩阵 A(G)，找出 u 和 v 在 G 中的最短距离 D(G)[u, v]。首先，不难发现如果 u <---> v 在原本图 G 的最短距离是 k，那麽在图 G^2 的最短距离只能是 ceil(k/2)。换句话说，若 D(G^2)[u, v] = t，那麽必定有 D(G)[u, v] = 2 * t 或 2 * t-1。究竟是奇数还是偶数呢？

Seidel 的决定性观察如下：如果是偶数 2t，那麽对於 u 的所有邻居 w，到 v 的距离都至少是 2t-1，此时将图平方後会得到 D(G^2)[w, v] >= t。如果是奇数 2 * t-1，那麽必定存在某个邻居 w (就是那个往 v 走一步的那个邻居 w)，在平方图上的距离严格变短 D(G^2)[w, v] = t - 1；而且，对於其他邻居，在平方图上的距离不会变长 D(G^2)[x, v] <= t。因此，我们只要把所有 u 的邻居 w (这需要原图的相邻矩阵的资讯)，到 v 的距离总和加起来，判断是否严格小於 D(G^2)[u, v] * degree(u)，就可以因此判定 D(G)[u, v] 到底是奇数还是偶数啦！

「把每个点 u 相邻的那些点 w，到 v 的距离加起来」这件事情，可以用另一个普通矩阵相乘做到！於是，如果采用不断平方直到图G变成完全图以後，慢慢展开回来的过程，我们就得到一个 O(n^ω log n) 时间复杂度的演算法了！