4.4.3 - Floyd-Warshall algorithm

• 可有負邊存在

1. 演算法

$A^k$為一個n*n矩陣， $A^{k}[i.j]$為 $i$ 到 $j$ 的shortest path length，途中經過的頂點編號必須≤$k$。

$A^0$為Cost Matrix，依序求出 $A^1, A^2,...,A^n$， $A^n$及為所求。

e.g.

$A^0= \begin{bmatrix} 0&4&11\\ 6&0&2\\ 3&∞&0 \end{bmatrix}$

$A^1= \begin{bmatrix} 0&4&11\\ 6&0&2\\ 3&7&0 \end{bmatrix}$

$A^2= \begin{bmatrix} 0&4&6\\ 6&0&2\\ 3&7&0 \end{bmatrix}$

$A^3= \begin{bmatrix} 0&4&6\\ 5&0&2\\ 3&7&0 \end{bmatrix}$