# Constructing a shortest path(The Floyd-Warshall algorithm)
## 目標
我們已經可以使用Floyd-Warshall algorithm解每個點到任意點最短路徑為多長，但我們還想知道是怎麼走到的
## 定義
我們定義一個矩陣$\Pi$，它包含元素$\pi_{ij}$，表示點i到點j他的parent
$\Pi^{(k)}$代表有經過k之後，節點的predecessor，所以也包含元素$\pi^{(k)}_{ij}$代表有經過k之後，點i到點j他的predecessor
## 演算法
使用DP
先考慮bounded condition
$$
\pi^{(0)}_{ij}=\left\{
\begin{array}{r}
NIL, & \text{if i=j or $w_{ij}=\infty$}\\
i, & \text{if i$\neq$j or $w_{ij}<\infty$}
\end{array}
\right.
$$
而其他情況，我們j的predecessor，會是我們最短路徑所來的節點i，在所有經過的節點{1,2,...,k-1}集合中。
when $k\geq1$
$$
\pi^{(k)}_{ij}=\left\{
\begin{array}{r}
\pi^{k-1}_{ij}, & \text{if $d^{(k-1)}_{ij}\leq d^{(k-1)}_{ik}+ d^{(k-1)}_{kj}$}\\
\pi^{k-1}_{kj}, & \text{if $d^{(k-1)}_{ij}> d^{(k-1)}_{ik}+ d^{(k-1)}_{kj}$}
\end{array}
\right.
$$
## 範例
$$
D^{(0)}=\begin{pmatrix}
0 & 3 & 8 & \infty & -4 \\
\infty & 0 & \infty & 1 & 7 \\
\infty & 4 & 0 & \infty & \infty\\
2 & \infty & -5 & 0 & \infty \\
\infty & \infty & \infty & 6 & 0
\end{pmatrix}
\ \Pi^{(0)}\begin{pmatrix}
NIL & 1 & 1 & NIL & 1 \\
NIL & NIL & NIL & 2 & 2 \\
NIL & 3 & NIL & NIL & NIL\\
4 & NIL & 4 & NIL & NIL \\
NIL & NIL & NIL & 5 & NIL
\end{pmatrix}
$$
$$
D^{(1)}=\begin{pmatrix}
0 & 3 & 8 & \infty & -4 \\
\infty & 0 & \infty & 1 & 7 \\
\infty & 4 & 0 & \infty & \infty\\
2 & 5 & -5 & 0 & -2 \\
\infty & \infty & \infty & 6 & 0
\end{pmatrix}
\ \Pi^{(1)}\begin{pmatrix}
NIL & 1 & 1 & NIL & 1 \\
NIL & NIL & NIL & 2 & 2 \\
NIL & 3 & NIL & NIL & NIL\\
4 & 1 & 4 & NIL & 1 \\
NIL & NIL & NIL & 5 & NIL
\end{pmatrix}
$$
$$
D^{(2)}=\begin{pmatrix}
0 & 3 & 8 & 4 & -4 \\
\infty & 0 & \infty & 1 & 7 \\
\infty & 4 & 0 & 5 & 11\\
2 & 5 & -5 & 0 & -2\\
\infty & \infty & \infty & 6 & 0
\end{pmatrix}
\ \Pi^{(2)}\begin{pmatrix}
NIL & 1 & 1 & 2 & 1 \\
NIL & NIL & NIL & 2 & 2 \\
NIL & 3 & NIL & 2 & 2\\
4 & 1 & 4 & NIL & 1 \\
NIL & NIL & NIL & 5 & NIL
\end{pmatrix}
$$
$$
D^{(3)}=\begin{pmatrix}
0 & 3 & 8 & 4 & -4 \\
\infty & 0 & \infty & 1 & 7 \\
\infty & 4 & 0 & 5 & 11\\
2 & -1 & -5 & 0 & -2 \\
\infty & \infty & \infty & 6 & 0
\end{pmatrix}
\ \Pi^{(3)}\begin{pmatrix}
NIL & 1 & 1 & 2 & 1 \\
NIL & NIL & NIL & 2 & 2 \\
NIL & 3 & NIL & 2 & 2\\
4 & 3 & 4 & NIL & 1 \\
NIL & NIL & NIL & 5 & NIL
\end{pmatrix}
$$
$$
D^{(4)}=\begin{pmatrix}
0 & 3 & -1 & 4 & -4 \\
3 & 0 & -4 & 1 & -1 \\
7 & 4 & 0 & 5 & 3\\
2 & -1 & -5 & 0 & -2\\
8 & 5 & 1 & 6 & 0
\end{pmatrix}
\ \Pi^{(4)}\begin{pmatrix}
NIL & 1 & 4 & 2 & 1 \\
4 & NIL & 4 & 2 & 1 \\
4 & 3 & NIL & 2 & 1\\
4 & 3 & 4 & NIL & 1 \\
4 & 3 & 4 & 5 & NIL
\end{pmatrix}
$$
$$
D^{(5)}=\begin{pmatrix}
0 & 1 & -3 & 2 & -4 \\
3 & 0 & -4 & 1 & -1 \\
7 & 4 & 0 & 5 & 3\\
2 & -1 & -5 & 0 & -2\\
8 & 5 & 1 & 6 & 0
\end{pmatrix}
\ \Pi^{(5)}\begin{pmatrix}
NIL & 3 & 4 & 5 & 1 \\
4 & NIL & 4 & 2 & 1 \\
4 & 3 & NIL & 2 & 1\\
4 & 3 & 4 & NIL & 1 \\
4 & 3 & 4 & 5 & NIL
\end{pmatrix}
$$