矩陣乘法在圖論中的簡單應用

08-09

矩陣乘法在圖論中的簡單應用

42 人贊了文章

雖然矩陣乘法通俗易懂，但其應用非常之多。

一、矩陣乘法實現

正如文章的標題處代碼所示，樸素的矩陣乘法實現起來寥寥幾行代碼。

假設要計算矩陣 $A in mathbb{R}^{n imes m}, B in mathbb{R}^{m imes n}$ 的乘積，那麼根據如下公式可以逐個元素計算

$C_{ij} = sum_{k=1}^m A_{ik} * B_{kj}$

時間複雜度 $O(n^2 m)$ 。

由於矩陣和圖密不可分，所以下面主要介紹一些矩陣在圖論中的應用。

二、鄰接矩陣

如下例子展示了圖到鄰接矩陣的對應關係。簡單的說，一張 $n$ 個節點的圖，可以用一個 $A in mathbb{R}^{n imes n}$ 的矩陣來表示，若節點 i，j 之間有邊相連，則 $A_{ij} = 1$ ；否則 $A_{ij} = 0$ 。

(圖片來源：http://btechsmartclass.com/DS/images/Graph%20Adjacency%20Matrix%201.jpg）

三、圖上最短路徑

求圖上最短路徑的演算法有：Dijkstra, Spfa 和 Floyd 等，這裡只講 Floyd 演算法。

由於要求得最短路徑的長度，所以這裡的鄰接矩陣並非 0/1 值，每個 entry 代表了這條邊的權重。給定鄰接矩陣，那麼 Floyd 演算法可以描述為：對每個節點對 (i, j), 每次嘗試選一個中間節點，更新 i 到 j 的最短路徑長度。代碼如下：

這裡會發現 Floyd 演算法和矩陣乘法的實現其實很像。

另外，如果問的是兩個點之間是否可達，而不需要計算其可達路徑長度，還可以使用 bitset 加速 Floyd 計算過程。

四、恰好經過 K 條邊互相可達的方案數

如果要求圖中兩個節點之間恰好經過 $k$ 條邊互相可達的方案數，那麼矩陣乘法也可以得到應用。假設已經得到了恰好經過 $k - 1$ 條邊的方案數矩陣 $B in mathbb{R}^{n imes n}$ , 同時還有初始的二值鄰接矩陣 $A in mathbb{R}^{n imes n}$ , 可以通過 $B imes A$ 得到恰好經過 $K$ 條邊互相可達的方案數矩陣。這裡可以得到結論：恰好經過 $k$ 條邊互相可達的方案數矩陣就是 $A^k$ 。於是乎，其代碼就是矩陣乘法的代碼，如果 $k$ 比較大，還可以通過矩陣快速冪加速。

五、恰好經過 K 條邊最短路徑

下面要解決的問題是：計算每個點對之間恰好經過 $k$ 條邊的最短路徑長度。

那麼我們可以將 Floyd 演算法和第四條中的結論結合起來。

其代碼和 Floyd 演算法的不同之處在於：Floyd 只對一個矩陣進行更新，而這裡需要對不同的矩陣進行操作。比如我們有 $A in mathbb{R}^{n imes n}$ 記錄恰好經過 $x$ 條邊的最短路徑矩陣， $B in mathbb{R}^{n imes n}$ 記錄恰好經過 $y$ 條邊的最短路徑矩陣，那麼就通過將兩者相乘得到 $C in mathbb{R}^{n imes n}$ , 為恰好經過 $x+y$ 條邊的最短路徑矩陣，同時用矩陣快速冪進行加速。