# Can the loops be in any order in the Floyd-Warshall algorithm?

I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if


Our professor told us that the loop for k MUST be outside the i and j loops. I am unable to understand why this must be the case. He said that if k is inside we will only compute the best 2 edged or 1 edge path from i to j. I just don't see it. Can someone help?

• Your professor is right that $k$ needs to be outside (check the correctness proof to see why), but wrong about the description of the output. It is only correct for $(i,j)=(1,2)$. – Yuval Filmus Dec 16 '20 at 8:49
• Sorry I misquoted him, now I have corrected it. But could you please write why k needs to be outside? – user123215321631443 Dec 16 '20 at 9:02
• Are you familiar with the analysis of Floyd–Warshall? Would the analysis work when $k$ is inside? – Yuval Filmus Dec 16 '20 at 9:03
• That is what I am unsure of. – user123215321631443 Dec 16 '20 at 9:04
• The professor is still wrong about what happens when $k$ is inside. When $(i,j) = (1,2)$ you are computing the best path of length at most $2$, but you are then allowed to use this best path for further computations. – Yuval Filmus Dec 16 '20 at 9:04

Suppose that you change the order of loops from $$k,i,j$$ to $$i,j,k$$. Let's see what happens when $$i=1$$ and $$j=2$$:

for k from 1 to |V|
if dist[1][2] > dist[1][k] + dist[k][2]
dist[1][2] ← dist[1][k] + dist[k][2]
end if
end for


It is not too hard to check that this puts in dist[1][2] the value $$\min_{1 \leq k \leq |V|} w(1,k) + w(k,2),$$ where $$w(1,1) = w(2,2) = 0$$. This is the cost of the shortest path of length at most $$2$$ from $$1$$ to $$2$$.

The $$(1,2)$$'th iteration is the only one which modifies dist[1][2], so at the end of the procedure, dist[1][2] will still contain $$\min_{1 \leq k \leq |V|} w(1,k) + w(k,2),$$ which could be arbitrarily off from the real shortest path from $$1$$ to $$2$$.

• Okay, so what I don't get is the following sentence: "This is the cost of the shortest path of length at most 2", Why? (1,k) and (k,2) could be paths longer than 2 right? – user123215321631443 Dec 16 '20 at 9:30
• No. At this point in the execution, dist[i][j] contains $w(i,j)$ (if $i \neq j$) or $0$ (if $i=j$). – Yuval Filmus Dec 16 '20 at 9:31
• Ahhhh, I see why this fails. So then if k is in the outer loop, how are we avoiding this situation? – user123215321631443 Dec 16 '20 at 9:33
• Sorry, I am taking some time to comment, I am trying to read again and again to understand it. – user123215321631443 Dec 16 '20 at 9:33
• I point you to the correctness proof of the algorithm. There is no need to repeat it here. The correctness proof explains why the algorithm is correct. – Yuval Filmus Dec 16 '20 at 9:34