Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The Floyd-Warshall algorithm is defined as follows:

   for k from 1 to |V|
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]

Why doesn't it work if I simply use

for i from 1 to |V|
  for j from 1 to |V|
     for k from 1 to |V|
        if dist[i][k] + dist[k][j] < dist[i][j] then
           dist[i][j] ← dist[i][k] + dist[k][j]

In this case, the intermediate node k is iterated in the innermost loop. I expect it will make the same comparisons, but maybe different order. Why is the result different and incorrect?

share|improve this question
    
What does this one do? next[i][j] ← k –  Pål GD Feb 10 '13 at 12:47
    
maybe to remember the path.. I just copied from wikipedia. We can I ignore it I guess, I am not interested in that part –  user6805 Feb 10 '13 at 13:46
1  
It is incorrect because the ordering is incorrect. The "different order" is what makes it incorrect. –  Paresh Feb 10 '13 at 14:24

2 Answers 2

Take $i - 1$ and $j = 2$. The algorithm is trying to find the shortest path between $1$ and $2$, by considering intermediate vertices. But at this point, most of the array dist is infinity, so we don't even find that $2$ is reachable from $1$ unless the distance is $1$ or $2$.

share|improve this answer

The approach of the algorithm is dynamic programming. This means that during computation only partial solutions are determined. Here $k$ is an important parameter in the algorithm. When dealing with $k$, shortest paths are computed that are only allowed to pass vertices $1$ upto $k$, the other vertices can only be initial or final. That means that $k$ has a different position than that of $i,j$. We cannot change that order. For a fixed $k$ however, the values $i,j$ within the inner two loops can be evaluated in ant order.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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