0
$\begingroup$

I try to wrap my head around the Floyd-Warshall algorithm, and I don't understand why the shortest path is guaranteed to be found since we check only the alternative connections up to one hop deep.

For example, let's consider the following graph with four vertices:

    A  B  C  D 
  A 0  5 -1  x
  B x  x  x  x
  C x  x  x -1 
  D x  3  x  x

The shortest path from A to B is A -> C -> D -> B and its weight is 1. However, AB is the first pair of vertices that are considered, so the connection C -> B is not yet in the table and the shortest distance is not relaxed from 5 to 1.

Am I missing something?

$\endgroup$

1 Answer 1

1
$\begingroup$

(Kleene-Roy-)Floyd-Warshall(-Ingerman)'s algorithm is defined iteratively, progressively increasing the number of allowed intermediate vertices.

  1. at the first step, no vertex is allowed as an intermediate. Since $(A, B)$ is an edge, $w(A, B) = 5$ is considered the minimum possible weight. Overall, the matrix of distances is the same as the weighted adjacency matrix: $$\begin{pmatrix}0&5&-1&\infty\\\infty&\infty&\infty&\infty\\\infty&\infty&\infty&-1\\\infty&3&\infty&\infty\end{pmatrix}$$
  2. at the second step, only vertex $A$ is allowed as an intermediate. The path $(A, A, B)$ is considered, but since $w(A, A) + w(A, B) = w(A, B)$, no modification is done. No other change is done to the matrix.
  3. at the third step, only $\{A, B\}$ are allowed as intermediates. No change is done to the matrix.
  4. at the fourth step, only $\{A, B, C\}$ are allowed as intermediates. There is now a possible path from $A$ to $D$: $$\begin{pmatrix}0&5&-1&-2\\\infty&\infty&\infty&\infty\\\infty&\infty&\infty&-1\\\infty&3&\infty&\infty\end{pmatrix}$$
  5. at the fifth and last step, all vertices are allowed as intermediates. Two changes result from that: there is now a path considered from $C$ to $B$, and there is a new path considered from $A$ to $B$, with lesser weight than the previous one. The matrix is updated: $$\begin{pmatrix}0&1&-1&-2\\\infty&\infty&\infty&\infty\\\infty&-4&\infty&-1\\\infty&3&\infty&\infty\end{pmatrix}$$

The idea with this dynamic programming algorithm is that a path from $s$ to $t$ using no other vertex than the $k$ first vertices as intermediates can be one of the two:

  • a path from $s$ to $t$ using no other vertex than the $k - 1$ first vertices as intermediates;
  • a path from $s$ to the $k$-th vertex followed by a path from the $k$-th vertex to $t$, both parts using no other vertex than the $k-1$ first vertices as intermidates.
$\endgroup$
1
  • $\begingroup$ Thank you for this answer. My confusion was because I mistook the order of the loop k. Iteration over k should be the most outer, not inner. $\endgroup$ Commented Nov 24, 2022 at 9:13

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.