3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ May I also ask you that even the $\prod^k[i,j]$ matrix can also be done this way such that the superscript $k$ can be removed and requires only one such $n\times n$ matrix to print out the shortest path? $\endgroup$ – Bit_hcAlgorithm Jan 5 at 14:49
  • $\begingroup$ For the same but more detailed explanation see here: stackoverflow.com/a/56156163/1267910 $\endgroup$ – Georgii Oleinikov May 15 at 19:28
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.