The Floyd-Warshall Algorithm

Every vertex $x$ either appears in a shortest path from a vertex $v$ to a vertex $w$, or it doesn’t.

• If there is such a path through $x$, we can express its length as the sum of the lengths of shortest $v-x$ and $x - w$ paths.
• If there is no $v - w$ shortest path through $x$, then we have a smaller subproblem on our hands, in which the set of candidate vertices that can appear as intermediate vertices of the shortest $v - w$ path is smaller (as it does not include $x$).

The central idea

Let’s think about the length of a shortest path from a vertex $v$ to $w$ whose intermediate vertices are confined to a set $\cal{I} \subseteq \textup{V}$.

Let’s say $d_{\cal{I}}\bigr[v\bigr]\bigr[w\bigr]$ is the length of a shortest possible $v-w$ path with intermediate vertices, if any, belonging to the set $\cal{I}$.

For example, in the following digraph with the vertex set $V$ containing five vertices and the set $\cal{I}$ of vertices shown in the cloud,

$$d_{\cal{I}}[v][w]=4$$

On the other hand, if the entire vertex set $V$ ...