> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/4-graph/4.4-shortest-path-length/4.4.3-floyd-warshall-algorithm.md).
# 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}$$