10.4 用矩陣角度看 APSP

從前兩天的文章可以看得出來，如果我們想要找出從 s 到 t 的最短路徑，可以透過枚舉中繼點 v 的方式來更新最短路徑的長度。也就是說 dist(s, t) = min { dist(s, u) + dist(u, t) }。如果我們想像一下把 “+” 看成乘法、取 min { dist(s, 1) + dist(1, t), dist(s, 2) + dist(2, t), … } 這件事情當成是 n 種選擇的加法，那麼整個計算過程就跟「矩陣相乘」非常類似。

事實上，我們稱這樣的矩陣運算為 (min, +)-矩陣相乘 ((min, +)-matrix multiplication)。
這麼一來，我們就可以利用數學式子將最短距離矩陣 D 與相鄰矩陣 A 連結再一起：
(這邊的相鄰矩陣的定義為：如果有一條邊從 i 連到 j 且權重為 w(i, j)，那麼會有 A[i, j] = w(i, j) ，如果沒有邊，那麼 A[i, j] = ∞，也就是定義成無窮大。此外我們定義 A[i, i] = 0，也就是自己走到自己是免費的。)

D = A^{n-1}

普通矩陣乘法(實數域)，是需要 O(n^ω) 次乘法計算的，而 ω 被定義為矩陣乘法常數(matrix multiplication exponent)，已知 2 <= ω <= 2.3728596。這個上界是 2020 年末才出爐的最新結果唷。但是這個 (min, +)-矩陣乘法相當奇怪，因為缺少 "加法反元素" 的關係，沒辦法簡單地套用普通矩陣乘法，而目前大家也還不知道 (min, +)-乘法能否做得比 O(n^2.9999999) 來得快。

APSP是否就只能就此作罷呢？當然不是，明天我們就來看幾個例子，利用實數(或是高精確度整數) 的普通矩陣乘法，在某些特殊情形下(比方說，這張圖的邊都沒有權重，權重都是 1 的情形) 求得 APSP。