# Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop

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?

• What does this one do? next[i][j] ← k Feb 10, 2013 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 Feb 10, 2013 at 13:46
• It is incorrect because the ordering is incorrect. The "different order" is what makes it incorrect. Feb 10, 2013 at 14:24

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

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.

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.

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 = min(inf, dist+dist, dist+dist, dist+dist)
= min(inf, inf, inf, inf)
= inf