Why can we drop the superscripts in the Floyd Warshall algorithm?

Question

In the lecture notes, our professor mentioned that we can take down the space taken by the FW algorithm from $O(n^3)$ to $O(n^2)$ by dropping all the superscripts in the matrices (i.e. use one $n\times n$ array $D$).

I just want to check my understanding, is it because by default $D^k=D^{k-1}$ except for the values $i,j$ where $d_{ik}^{k-1}+d_{kj}^{k-1}<d_{ij}^{k-1}$ where we set $d_{ij}^k=d_{ik}^{k-1}+d_{kj}^{k-1}$ but in essence we are using the values in the $D^{k-1}$ matrix to update itself?

However, what if we change one value, say $d_{i_1j_1}^k$ in the $kth$ iteration but then we need to reuse the value $d_{i_1j_1}^{k-1}$ later on in the same $kth$ iteration, wouldn't it be lost?

Answer 1

Basically in iteration k no entry $d_{ij}$ can change if $i=k$ or $j=k$. Since you update the entries in $D$ by considering $d_{ik}$ and $d_{kj}$ you can do all these updates in-place.

However there is an even simpler argument if you only want to show that the algorithm requires $O(n^2)$ space. At every iteration $k$ the values in $D^k$ only depend on the previous matrix $D^{k-1}$. Therefore it is enough to store the matrix $D^{k-1}$ of the previous iteration, use it to fill the next matrix $D^k$ and then you can safely discard $D^{k-1}$. So you only ever need to keep two matrices in memory and arrive at $O(n^2)$ space. Of course no sensible implementation would actually do this but it is enough to show the space bounds.

Answer 2

The reason is that the numbers $d_{ik}$ and $d_{kj}$ do not change when computing matrix $D^k$; distances either starting or ending in $k$ cannot be improved by looking for a path that travels via $k$ (or equivalently, $d_{kk}=0$).

The right-hand side of the instructions of the algorithm only involve these numbers on the $k$-th row and column. The algorithm will not change them. The other numbers are recomputed but not used, so can be overwritten in $D^{k-1}$ to get $D^k$.