All-Pairs Shortest Paths with Matrix Multiplication Method

使用一個矩陣(adjacency matrix)W來表示graph，
接著計算一系列的矩陣L⁽¹⁾、L⁽²⁾、...、L^(n-1)，
其中L⁽¹⁾ = W，L^(n-1)代表最後的計算結果。

W = (w_ij)，L^(m) = (l_ij^(m))，m=1...n-1。
(l_ij^(m))代表從vertex i到vertex j、包含最多m條edge、
weight最小的任何一條path。

接著要計算：
L⁽¹⁾ = L⁽⁰⁾．W = W¹
L⁽²⁾ = L⁽¹⁾．W = W²
...
L^(n-1) = L^(n-2)．W = W^n-1

因為我們最後需要得到的矩陣是L^(n-1)，
所以不需要去計算中間過程的每一個矩陣，
我們可以只計算2的次方數的矩陣以加速運算，
因此計算L^(n-1)只需要做 ceiling[lg(n-1)] 次的矩陣乘法運算即可。
 
L⁽¹⁾ = W
L⁽²⁾ = W² = W．W
L⁽⁴⁾ = W⁴ = W²．W²
L⁽⁸⁾ = W⁸ = W⁴．W⁴
...
L^{(2*ceiling[lg(n-1)])} = W^{2*ceiling[lg(n-1)]} = W^{2*ceiling[lg(n-1)]-1}．W^{2*ceiling[lg(n-1)]-1}

這邊用SLOW-ALL-PAIRS-SHORTEST-PATH當做例子，
實際算一次。

L⁽¹⁾就是一開始的Graph，
記錄每個點「走一步」到其他點的距離。

例：
L⁽²⁾ = L⁽¹⁾．W = L⁽¹⁾．L⁽¹⁾
L⁽²⁾(1,4) = min {0+∞, 3+1, 8+∞, ∞+0, -4+6} = 2

例：
L⁽³⁾ = L⁽²⁾．L⁽¹⁾
L⁽³⁾(2,3) = min {3+8, 0+∞, -4+0, 1+(-5), 7+∞} = -4

例：
L⁽⁴⁾ = L⁽³⁾．L⁽¹⁾
L⁽⁴⁾(5,2) = min {8+3, 5+0, 1+4, 6+(-1), 0+∞} = 5

Introduction to Algorithms Fig. 25.1