patternMinor
Why can we drop the superscripts in the Floyd Warshall algorithm?
Viewed 0 times
floydwhythesuperscriptscanwarshalldropalgorithm
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#74870, answer score: 5
Revisions (0)
No revisions yet.