This problem is concerned with the graph below.

Recall that the recursive formula for the distances computed by the Floyd$-$Warshall APSP algorithm

defines an entry $(i,j)$ in the $k$ th $D-$matrix as follows:

$,d_{ij}^{(k)}=w_{ij}ifk=0$ and

min$(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$ otherwise.

When $k=0,$ we also need to consider when there is no edge from $i$ to $j.$ So we also have $d_{ij}^{(0)}=0$ if

$i==j$ and $$ if $ij$ but there is no edge from $i$ to $j.$

$($a$)$ Fill in the first two $D$ matrices, $D^{(0)}$ and $D^{(1)}$ following the recursive formula above.

Solution:

$($b$)$ We're now interested in $,$ the predecessor matrix that would help us construct a shortest

path between any two vertices. We define a value ${}_{ij}^{(k)}$ in the predecessor matrix ${}^{(k)}$ as ${}_{ij}^{(k)}=$

predecessor of vertex $j$ on a shortest path from vertex $i.$

Give a formula for ${}_{ij}^{(0)},$ the entry for $i,j$ in the initialization matrix.

Solution:

$($c$)$ Give a recursive formula for entry $(i,j)$ in the $k$ th $$ matrix. You can assume all relevant $D$

matrices exist and you can refer back to them.

Solution: