Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
According to CLRS, each iteration of the outermost loop (on $k$) makes a new copy of the adjacency matrix. Is it safe not to copy the matrix on every iteration?
What I mean is, according to CLRS:
$d_{ij}^K = \min(d_{ij}^{K-1}, d_{ik}^{K-1} + d_{kj}^{K-1})$
Is the following possible?
$d_{ij} = \min(d_{ij}, d_{ik} + d_{kj})$
I have tried not copying the matrix, and got the same result before as the one which makes a copy after each iteration, but did I just get lucky?
No you are not lucky, it is possible to use the program that way. The notation $d_{ij}^k$ probably is used for better explaining what the algorithm has achieved in the $k$th step. Note that the variant where one overwrites the matrix as you suggest is presented in Exercise 25.2-4 (in my second edition of the book, which is not the latest).
The secret to that puzzle is in principle that an assignment to $d_{i,j}^k$ is only done once, and that value is never again used in the computation, except for the case where either $i=k$ or $j=k$. However, the algorithm does not change those values in the $k$th step. You figure out why.
