1
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Dec 16 '20 at 8:49
  • $\begingroup$ Sorry I misquoted him, now I have corrected it. But could you please write why k needs to be outside? $\endgroup$ – user123215321631443 Dec 16 '20 at 9:02
  • $\begingroup$ Are you familiar with the analysis of Floyd–Warshall? Would the analysis work when $k$ is inside? $\endgroup$ – Yuval Filmus Dec 16 '20 at 9:03
  • $\begingroup$ That is what I am unsure of. $\endgroup$ – user123215321631443 Dec 16 '20 at 9:04
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 16 '20 at 9:04
1
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – user123215321631443 Dec 16 '20 at 9:30
  • $\begingroup$ No. At this point in the execution, dist[i][j] contains $w(i,j)$ (if $i \neq j$) or $0$ (if $i=j$). $\endgroup$ – Yuval Filmus Dec 16 '20 at 9:31
  • $\begingroup$ Ahhhh, I see why this fails. So then if k is in the outer loop, how are we avoiding this situation? $\endgroup$ – user123215321631443 Dec 16 '20 at 9:33
  • $\begingroup$ Sorry, I am taking some time to comment, I am trying to read again and again to understand it. $\endgroup$ – user123215321631443 Dec 16 '20 at 9:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 16 '20 at 9:34

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.