5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

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