Floyd-Warshall Correctness And Negative Cycles

What the Floyd–Warshall Tables Mean

Floyd–Warshall updates a distance table in stages. At stage \(k\), it allows vertex \(k\) to be used as an intermediate vertex, in addition to the vertices already allowed. The key correctness question is whether these table entries really are shortest-path distances. The answer depends on the absence of negative cycles: with no negative cycle, the final table gives all shortest distances. If a negative cycle is present, a negative diagonal entry records that fact.

Throughout, consider a finite, loopless directed graph with a real weight \(w(u,v)\) on each directed edge. There is at most one edge for each ordered pair of vertices. A directed walk is a sequence of vertices in which each consecutive pair is joined by a directed edge; its weight is the sum of the weights of its edges. A directed path has no repeated vertices. A directed cycle is a positive-length closed directed walk with no repeated vertices except its first and last vertex. A negative cycle is a directed cycle whose total weight is negative. The empty walk from a vertex to itself has weight zero. We use \(+\infty\) for a pair with no available walk.

In this formula, a sum involving \(+\infty\) is \(+\infty\). The first candidate keeps a route that does not use \(k\) internally; the second joins a route from \(i\) to \(k\) to one from \(k\) to \(j\). The earlier material on the intermediate-vertex recurrence develops this update. Here we justify its distance interpretation and establish what happens when negative cycles exist.

Why the Final Table Gives Shortest Distances

First, a basic consequence of having no negative cycles is that shortest distances exist whenever a destination is reachable. Any closed directed walk can be split into directed cycles: if it repeats a vertex other than the repeated endpoints, split at two occurrences of that vertex into shorter closed walks, and continue. The weights of the resulting cycles add to the weight of the original walk. Thus, if there is no negative cycle, every closed directed walk has nonnegative weight.

Now take any walk from \(i\) to \(j\) that repeats a vertex. The part between two occurrences of the same vertex is a closed walk, so it has nonnegative weight. Removing that part leaves a walk with the same endpoints and no greater weight. Repeating this removal gives a path, or the empty walk if \(i=j\). There are only finitely many paths in a finite graph, so if \(j\) is reachable from \(i\), a path of minimum weight exists. If \(i=j\), the empty walk has minimum weight zero, since every closed walk has nonnegative weight.

Proof. We use induction on \(k\). For \(k=0\), a walk with no internal vertices is either the empty walk from a vertex to itself, a single edge, or nonexistent. These possibilities give exactly the entries of \(D^{(0)}\).

Assume the assertion holds at stage \(k-1\). Consider first distinct endpoints \(i\ne j\). By the preceding argument, a minimum-weight walk subject to the allowed intermediate vertices can be chosen to be a path. If this path does not contain \(k\) internally, its weight is at least \(D^{(k-1)}_{ij}\), and the induction hypothesis says that this candidate is attainable when finite. If it does contain \(k\), it contains \(k\) only once, because it is a path. Splitting at \(k\) gives an \(i\)-to-\(k\) path and a \(k\)-to-\(j\) path whose internal vertices are all among \(1,\dots,k-1\). By induction, their minimum weights are \(D^{(k-1)}_{ik}\) and \(D^{(k-1)}_{kj}\). Their concatenation is a permitted walk through \(k\), with weight equal to the sum of those entries. Taking the smaller of the two cases gives the recurrence.

For \(i=j\), the empty walk has weight zero and is permitted at every stage. Every other permitted walk from \(i\) back to \(i\) is closed and has nonnegative weight, because there is no negative cycle. Therefore the minimum is zero. The recurrence also returns zero: its first candidate is \(D^{(k-1)}_{ii}=0\) by induction, and its second candidate, if finite, is the weight of a closed walk formed by joining an \(i\)-to-\(k\) walk to a \(k\)-to-\(i\) walk. That weight is nonnegative. This proves the assertion for equal endpoints as well. At \(k=n\), every vertex is allowed as an intermediate vertex, proving the final claim. \(\square\)

Worked Tables Without Negative Cycles

Negative Cycles and the Diagonal

When a negative cycle is reachable from a vertex and can return to it, closed walks through that vertex can be made arbitrarily negative by repeating the cycle. There is then no finite shortest distance for that pair. Floyd–Warshall’s final diagonal detects the presence of such a cycle anywhere in the graph, whether or not every vertex can reach it.

Proof. First suppose there is a negative cycle \(C\). We show that the recurrence can represent its weight in a diagonal entry. More precisely, for every \(k\), it gives an entry no greater than the weight of any simple directed path whose internal vertices have labels at most \(k\), and no greater than the weight of any simple directed cycle rooted at \(i\) whose internal vertices have labels at most \(k\). At \(k=0\), the path claim follows from the direct-edge entries, and there is no loopless cycle with no internal vertices.

For the induction step, take either such a path or such a cycle. If \(k\) is not an internal vertex, the induction hypothesis applies at \(k-1\), and the recurrence never increases an entry because it takes a minimum including the previous entry. If \(k\) is internal, it occurs exactly once. For a path, split it at \(k\) into two simple paths; for a cycle rooted at \(i\), split it at \(k\) into a path from \(i\) to \(k\) and a path from \(k\) back to \(i\). Each piece has internal vertices labelled at most \(k-1\). By induction, the corresponding \(D^{(k-1)}\) entries are no greater than the weights of the pieces. The recurrence’s through-\(k\) candidate is therefore no greater than their sum, which is the original path or cycle weight. This proves the claim.

Choose \(k\) to be the largest vertex label on \(C\), and root \(C\) at a vertex \(i\) on it. The claim gives \(D^{(k)}_{ii}\le w(C)<0\). Since later stages never increase entries, \(D^{(n)}_{ii}<0\).

Conversely, every finite entry produced by the recurrence is the weight of an actual directed walk: this holds initially, and a finite through-\(k\) candidate concatenates two walks represented at stage \(k-1\). Thus \(D^{(n)}_{ii}<0\) gives a negative closed walk. If a closed walk is not a simple cycle, splitting it at a repeated vertex expresses its weight as the sum of the weights of two shorter closed walks. A negative sum has at least one negative summand. Repeating this splitting eventually yields a negative simple directed cycle. This proves the converse. \(\square\)

Reading the Result Correctly

With no negative cycle, the diagonal of the final table is zero, and every finite off-diagonal entry is a shortest distance. A value \(+\infty\) means there is no directed route between that ordered pair. With a negative cycle, a negative diagonal entry is a certificate that shortest distances are not well-defined for all pairs in the ordinary finite sense. The table’s other entries should not then be interpreted as a complete all-pairs shortest-distance solution.

Common mistake. A negative edge is not by itself evidence of a negative cycle. In the first example, the edge \(2\to3\) has weight \(-2\), but every directed cycle has positive weight, and the final diagonal remains zero. Conversely, checking only whether an input edge has negative weight cannot establish that the graph is safe. The relevant test is the diagonal after all vertices have been allowed: a negative entry means a negative cycle exists. Do not confuse this with a negative off-diagonal distance, which can occur even when there is no negative cycle.