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

4 Answers 4

6
$\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$
4
$\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$
1
$\begingroup$

Here is an example when for k being the inner most loop doesn't work:

0 -- 2 -- 3 -- 1

Say each edge weight is 1. The corresponding adjacency matrix is:

Node 0 1 2 3
0 0 inf 1 inf
1 inf 0 inf 1
2 1 inf 0 1
3 inf 1 1 0

The final distance for 0 and 1 is inf, which is incorrect:

dist[0][1] = min(inf, dist[0][1]+dist[1][1], dist[0][2]+dist[2][1], dist[0][3]+dist[3][1])
           = min(inf, inf, inf, inf)
           = inf
$\endgroup$
0
$\begingroup$

Initially

dist[i][j] = AdjacentMatrix[i][j] //all directly reachable nodes are the base case.

How more can we improve on the base case?

Two possible algorithms which can work.

  1. Find dist[i][j] = For all k { dist[i][k] + dist[k][j] }

    This doesn't work because dist[i][k] can still be INF and is not finalized.

  2. Fix one intermediate node k1 & find all dist[i][j] passing through intermediate node.

    On the second intermediate node k2, Find dist[i][j] = min { dist[i][k1] + dist[k1][j] , dist[i][k2] + dist[k2][j] }

    In this algorithm, although dist[i][k] is not finalized, it is OK. Because value of dist[i][j] is finalized only when dist[i][kn] is compared.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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