iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
Software Development

圖論與演算法之間的相互應用系列 第 15

最短路徑問題 (3)

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。


上一篇
最短路徑問題 (2)
下一篇
最短路徑問題 (4)
系列文
圖論與演算法之間的相互應用30

尚未有邦友留言

立即登入留言