Q12

Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a directed graph $G$ with $n*n$ adjacency matrix $A$. $A[i,j]$ equals $1$ if there is an edge in $G$ from $i$ to $j$, and $0$ otherwise. Your aim in filling in the blanks is to ensure that the algorithm is correct. INITIALIZATION: For i = 1 ... n {For j = 1 ... n { if a[i,j] = 0 then P[i,j] =_______ else P[i,j] =_______;} } ALGORITHM: For i = 1 ... n {For j = 1 ... n {For k = 1 ... n {P[__,__] = min{_______,______}; } } }