3
$\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?

$\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$ Commented Dec 16, 2020 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$ Commented Dec 16, 2020 at 9:02
  • $\begingroup$ Are you familiar with the analysis of Floyd–Warshall? Would the analysis work when $k$ is inside? $\endgroup$ Commented Dec 16, 2020 at 9:03
  • $\begingroup$ That is what I am unsure of. $\endgroup$ Commented Dec 16, 2020 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$ Commented Dec 16, 2020 at 9:04

3 Answers 3

2
$\begingroup$

The pseudocode came from Wikipedia and the explanation is in Wikipedia as well. The recurrence is $dist(i, j, k) = min(dist(i,j,k-1),\ dist(i,k,k-1) + dist(k,j,k-1))$ with the base case $dist(i, j, 0) = w(i, j)$. There is only one way we can achieve this iteratively, by calculating all cases of $k-1$ before calculating cases of $k$. The other answer has an example when this is broken.

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

$\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$ Commented Dec 16, 2020 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$ Commented Dec 16, 2020 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$ Commented Dec 16, 2020 at 9:33
  • $\begingroup$ Sorry, I am taking some time to comment, I am trying to read again and again to understand it. $\endgroup$ Commented Dec 16, 2020 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$ Commented Dec 16, 2020 at 9:34
0
$\begingroup$

The order of the loops in the Floyd-Warshall algorithm is crucial. The algorithm works by progressively improving an estimate of the shortest path between every pair of vertices by considering each vertex as a possible intermediate step on the path.

If you change the order of the loops such that k (the intermediate vertex) is considered last, the algorithm will not work correctly. This is because when you calculate dist[i][j], you're assuming that you've already considered all possible intermediate vertices that could provide a shorter path. If k is considered last, then you're not actually considering all possible intermediate vertices before updating dist[i][j].

So, altering the order of loops to i, j, k will not yield the correct shortest paths between all pairs of vertices. The correct order is k, i, j as in the original Floyd-Warshall algorithm.

$\endgroup$
1
  • $\begingroup$ This answer is less precise than the existing ones. $\endgroup$
    – Kai
    Commented Jan 24 at 23:27

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.