Problem Detail: 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?
Asked By : peteykun
Answered By : Hendrik Jan
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18389 Ask a Question Download Related Notes/Documents
