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) 時間複雜度的演算法了！