The Floyd-Warshall Intermediate-Vertex Recurrence

Restricting Which Vertices a Path May Use

Single-source methods organize shortest paths around a starting vertex. The Floyd–Warshall method instead builds an all-pairs table in stages: at stage \(k\), it allows paths to use one more vertex as an internal vertex. The key observation is that a shortest path either avoids this newly allowed vertex or passes through it, in which case its cost splits into two shorter costs.

Throughout, let \(G\) be a finite directed graph with no loops or parallel arcs, and assign a real weight \(w_{ij}\) to each arc \(i\to j\). Negative edge weights are allowed. Assume that \(G\) has no directed cycle of negative total weight. This assumption ensures that shortest-walk costs are finite whenever a destination is reachable. A walk's cost is the sum of the weights of its arcs; a path is a walk with no repeated vertices. The internal vertices of a walk are all its vertices except its first and last vertices.

The index \(k\) records which vertices are permitted internally, not how many edges a path may use. In particular, the endpoints \(i\) and \(j\) are not restricted by \(S_k\). This distinction matters when an endpoint itself has an index larger than \(k\).

Why Shortest Paths Can Be Chosen Without Repeated Vertices

Proof. Any walk with a repeated vertex contains a nonempty closed subwalk between two occurrences of that vertex. A closed directed walk can be split into directed cycles by repeatedly splitting it at repeated vertices. Since the graph has no negative-weight directed cycle, each of those cycles has nonnegative cost, so the closed subwalk has nonnegative cost. Removing it leaves a walk with the same endpoints, no greater cost, and fewer arcs. Repeating this removal gives a path. There are only finitely many paths in a finite graph, so among the paths satisfying the internal-vertex restriction, a minimum-cost one exists whenever that set of paths is nonempty. Removing a closed subwalk cannot introduce new internal vertices, so the restriction is preserved. \(\square\)

This lemma also covers \(i=j\): the length-zero walk has cost \(0\), and every nonempty closed walk has nonnegative cost. Thus the shortest cost from a vertex to itself is \(0\). The no-negative-cycle assumption is important: if a negative cycle can be reached and then left on a route to a destination, repeated trips around it make the walk costs arbitrarily small, so a finite minimum need not exist.

Initialization and the Intermediate-Vertex Recurrence

When vertex \(k\) becomes available internally, a shortest path either avoids \(k\), leaving its cost at \(D^{(k-1)}_{ij}\), or uses \(k\). In the latter case, the path can be split at \(k\): the part from \(i\) to \(k\) and the part from \(k\) to \(j\) use only vertices in \(S_{k-1}\) internally.

Proof. Fix \(k,i,j\). First consider any walk from \(i\) to \(j\) whose internal vertices belong to \(S_k\). By the lemma, a minimum-cost such walk can be chosen to be a path. If this path does not have \(k\) as an internal vertex, then its internal vertices belong to \(S_{k-1}\), so its cost is at least \(D^{(k-1)}_{ij}\). If it does have \(k\) internally, the path visits \(k\) exactly once. Splitting at \(k\) gives an \(i\)-to-\(k\) path and a \(k\)-to-\(j\) path whose internal vertices lie in \(S_{k-1}\). Their costs are at least \(D^{(k-1)}_{ik}\) and \(D^{(k-1)}_{kj}\), respectively. Thus the minimum cost allowed at stage \(k\) is at least the stated minimum.

For the reverse inequality, a walk achieving \(D^{(k-1)}_{ij}\), when finite, is still allowed at stage \(k\). Also, if both \(D^{(k-1)}_{ik}\) and \(D^{(k-1)}_{kj}\) are finite, concatenate paths achieving them. The resulting walk has internal vertices in \(S_k\), so its cost \(D^{(k-1)}_{ik}+D^{(k-1)}_{kj}\) is an available cost at stage \(k\). Therefore \(D^{(k)}_{ij}\) is no greater than either finite candidate. If a candidate is infinite, it supplies no route and does not affect the minimum. Combining the two inequalities proves the recurrence. \(\square\)

The proof includes endpoint cases. For example, if \(i=k\), the candidate through \(k\) uses \(D^{(k-1)}_{kk}=0\), so it does not create a spurious improvement. Every stage uses the previous stage's entries; conceptually, all entries for one \(k\) are updated from the same table \(D^{(k-1)}\).

Worked Tables

Reading the Table and Avoiding Common Errors

After stage \(k\), the entry \(D^{(k)}_{ij}\) represents the best cost among routes whose internal vertices lie in \(\{1,\dots,k\}\). Once all vertices have been admitted, \(D^{(n)}\) is the all-pairs distance table under the stated no-negative-cycle assumption. The vertex order determines the intermediate tables, but the final restriction includes every vertex, so the final entries represent unrestricted shortest distances.

A common mistake is to confuse the index of the newly allowed intermediate vertex with an endpoint, or to use entries from the wrong stage. The update for stage \(k\) always uses \(D^{(k-1)}_{ik}\) and \(D^{(k-1)}_{kj}\); it does not use an arbitrary direct edge or an entry from a later stage. For a diagonal update such as \(i=j=k\), the candidate is \(D^{(k-1)}_{kk}+D^{(k-1)}_{kk}=0+0=0\), not a sum involving unrelated entries. Another frequent error is treating \(+\infty\) as an ordinary real number: it records that a route is unavailable, and adding it to a finite cost still gives \(+\infty\).

The recurrence is the structural reason the method is compact: every new table is obtained by comparing a route that avoids \(k\) with one that passes through \(k\). The proof establishes the meaning of each restricted table entry; further questions, including how negative cycles affect the computation, require separate care.