2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

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