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

New contributor
sparco is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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.