Motivation
A single-source shortest-path algorithm answers distances from one starting vertex. Sometimes distances between every ordered pair are needed. Floyd–Warshall organizes the problem around which vertices may occur inside a path. At each stage it asks whether allowing one more intermediate vertex improves a distance.
Negative edges are allowed in this unit, but negative cycles are not. Without that assumption a shortest finite distance need not exist: repeatedly traversing a reachable negative cycle can drive a walk's weight downward without bound. We treat unreachable pairs as having distance .
Definitions
Definition 3.6.1
(Distances through intermediate vertices)
Let be a finite directed graph on vertices , with real edge weights and no negative-weight directed cycle. Parallel edges may be replaced by their minimum weight. A walk's weight is the sum of its edge weights. A length-zero walk from a vertex to itself has weight zero. For , define as the minimum weight of a walk from to whose internal vertices belong to ; endpoints are not restricted. If no such walk exists, the value is .
Initialize and for to the lightest direct-edge weight or if no edge exists. With no negative cycles, a self-loop has nonnegative weight and the zero-length diagonal initialization is correct. Use for finite when evaluating a candidate.
Theorems
Theorem 3.6.2
(Intermediate-vertex recurrence)
For ,
After stage , these entries are all-pairs shortest-walk distances.
Theorem 3.6.3
(In-place computation)
Starting from , process and, for every ordered pair , replace by . Under the no-negative-cycle hypothesis, the result equals . This uses arithmetic/comparison operations and distance entries.
Proof sketch or proof idea
Proof
(Splitting a shortest path at the new vertex)
With no negative cycles, a minimum-weight permitted walk exists whenever any permitted walk exists: remove repeated-vertex cycles of nonnegative weight until a simple path remains. If a shortest path has no internal occurrence of , its cost is at least . Otherwise choose a shortest simple path, which visits at most once, and split it at . Both subpaths have internal vertices among , so its cost is at least . The same reasoning includes the case where is an endpoint, using a zero-length subwalk.
Conversely, any walks realizing the two second-term distances can be concatenated at to form an allowed walk for stage . The first-term walk is also allowed. If a term is infinite, it supplies no finite candidate. These two inequalities prove the recurrence. At stage every vertex is allowed internally, giving unrestricted shortest-walk distances.
Proof X-ray
Where the no-negative-cycle hypothesis enters
The non-obvious move is to choose a shortest simple path before splitting: only then does occur at most once, so the two halves are well defined and each has its internal vertices among . The no-negative-cycle hypothesis is used here, to show that removing a cycle never increases the weight, so that a simple minimizer exists. The matching upper bound needs no such care, because concatenating two permitted walks at gives a permitted walk even if the result repeats vertices. The argument closes by induction on the stage , starting from the direct-edge table at stage zero, and at stage no restriction on internal vertices remains. Without the hypothesis the split is meaningless, since no minimum exists, as the counterexample below shows.
Proof
(The row and column stay fixed within a stage)
For in-place updates, every diagonal remains zero because a negative closed walk would contain a negative cycle, excluded by hypothesis. At stage , the update of compares it with ; the update of similarly leaves it unchanged. Thus throughout that stage the row and column used for candidates retain their stage- values. Each other cell is updated once from its previous value using those unchanged entries, exactly implementing the recurrence regardless of the order of pairs. Three nested loops give the operation bound and the table has entries.
Proof X-ray
Why in-place updates are safe here
The proof needs the stage- row and column to remain unchanged while other cells are updated. The zero diagonal, guaranteed by the no-negative-cycle assumption, supplies that invariant.
Worked examples
Worked example 3.6.4
(An intermediate vertex improves a path)
Suppose has weight , has weight , and has weight . Allowing as an intermediate vertex offers the candidate , so the distance from to becomes one. A negative edge is harmless to this reasoning when no negative cycle exists.
Worked example 3.6.5
(An unreachable pair)
If neither a direct edge nor any walk reaches from , every candidate involving an unreachable segment has value . The final entry remains . It must not be replaced by a large finite number without proving that number exceeds every relevant finite path cost.
Common mistakes
Common mistake
(Treating every negative edge as a negative cycle)
An edge of weight need not invalidate a shortest-path problem. The problem arises when a reachable cycle can be repeated with negative total weight. The worked example with has a negative edge but no cycle in its displayed graph.
Counterexample mode
Dropping the no-negative-cycle hypothesis
Claim: the recurrence computes shortest-walk distances for every real-weighted directed graph, negative cycles included. Take two vertices with an edge of weight and an edge of weight , a cycle of weight . Repeating it produces walks from to itself of weights , so no finite minimum exists for that pair. The in-place algorithm, run with the pairs in row-major order, starts from and ends with . The diagonal entries are negative, so the table is not a table of distances, and its values depend on how far the loops happen to run. The repair is the hypothesis: no directed cycle of negative weight, or else a separate algorithm that detects such cycles.
The theorem computes distances; reconstructing a path needs additional predecessor information and careful tie handling.
Counterexample mode
Putting the stage index innermost
Claim: the three loops can be nested in any order, for instance with innermost, and a single pass still gives the distances. Take vertices with edges , and , all of weight , so the distance from to is . With innermost and the pairs in row-major order, entry is evaluated before and have received their improved values and . Its candidates are and , so it stays , and row is never revisited. The repair is the stated nesting, with the stage outermost, which finishes every pair for stage before stage begins.
Reading the state correctly
The index limits internal vertices, not endpoints. At stage zero, a direct edge has no internal vertex and is permitted even if either endpoint has a large label. The length-zero walk is also permitted. At stage , the endpoints and may equal ; the recurrence remains valid because the diagonal distance is zero under the hypothesis.
The dynamic-programming invariant is: after completing stage , each table entry is the best distance using only vertices internally. It is not a statement that those vertices must all be used. Allowing an additional vertex can only preserve or improve a distance, so . A computation that raises a finite entry has violated the recurrence.
Worked example 3.6.6
(A complete three-vertex table)
Let the vertices be in that order, with edges of weight , of weight , of weight , and of weight . The two directed cycles have weights and , so there is no negative cycle. The initial table is
Allowing makes cost . Allowing makes cost . Allowing makes cost . The final table is
The entries not mentioned remain unchanged. Each improvement is justified by an actual concatenated walk.
Concept lensAlgebraic
The same table as a matrix product
Replace addition by minimum and multiplication by addition: the product of two tables is . With the initial table, lists the best walks of at most two edges, and lists those of at most edges, which suffices because shortest walks may be taken simple. Hence in this product. In the three-vertex example, already equals the final table.
A table entry can have several minimizing walks. The recurrence needs only the minimum weight, so ties can be left unchanged. If a path is also requested, a separate witness structure can record a direct edge or an improving intermediate vertex. Reconstructing from a final in-place table requires an invariant for those witnesses, especially when zero-weight cycles or tied paths exist. This unit proves the distance computation; it does not claim a particular path-reconstruction implementation is correct.
Why cycles can be removed
Any closed walk can be decomposed into directed cycles. Under the hypothesis, each such cycle has nonnegative weight, so removing a repeated-vertex closed segment cannot increase the walk's total weight. Repeating this operation produces a simple path between distinct endpoints, or the empty walk when the endpoints coincide. Removing vertices cannot introduce an internal vertex outside the permitted set. Since a finite graph has only finitely many simple paths between a fixed pair, a minimum exists whenever the pair is reachable.
This argument allows zero-weight cycles. Removing one may leave the same weight rather than a strictly smaller one, but it still yields a simple minimizer. Negative edges are also permitted: what matters is the total weight of every directed cycle. A shortest simple path can contain a negative edge as long as no repeatable negative closed walk makes the infimum unbounded below.
The recurrence's upper-bound direction uses concatenation, which may create a walk with repeated vertices even when each component is simple. That is allowed in the definition of . The concatenated walk respects the internal-vertex restriction: the joining vertex is , and all other internal vertices occur in one of the two subwalks. If desired, nonnegative cycles can then be removed without increasing its weight. This is why the two inequalities fit together without assuming the concatenation itself is simple.
The three loop indices
The outer index determines the set of permitted intermediate vertices. For fixed , the two inner loops enumerate all start and end vertices. Because the th row and column do not change during that stage, either order of those inner loops works under the theorem's assumptions. Moving inside the other loops no longer guarantees that every pair sees all paths in the intended sequence; it needs a different proof and can give a different result.
The no-negative-cycle hypothesis is used twice: it ensures finite minima exist for reachable pairs and it makes throughout the in-place computation. It is not merely a reason to reject negative input edges. If a graph may contain negative cycles, one must specify whether the desired result is detection, finite distances for unaffected pairs, or for pairs that can reach and leave such cycles. Those are related but different output specifications, and their algorithms require additional proof.
Representing infinity and measuring cost
Common mistake
(Using a finite sentinel for infinity)
A mathematical is a special value, not an ordinary integer. In code, a guarded addition can return infinity whenever either summand is infinite. Using a fixed large sentinel and adding a negative edge weight to it can produce a misleading finite value unless overflow and all finite-distance bounds are controlled. The exact-real recurrence avoids that representation issue; an implementation must address it explicitly. For example, let stand for infinity. If cannot reach but there is an edge of weight , the candidate is smaller than , and an unreachable pair is given a finite distance.
The count treats additions and comparisons of finite edge weights as unit operations. With rational weights encoded in binary, their exact arithmetic costs and bit lengths must also be considered. The method stores a dense table even if the original graph has few edges; repeated single-source algorithms may have different resource tradeoffs. The theorem does not claim that a dense all-pairs table is always the most efficient representation.
For with no negative self-loop, initialization gives the one-by-one table and the only stage leaves it unchanged. For disconnected graphs, some entries remain infinite while others are finite. These cases are part of the same invariant; no artificial path between components is introduced.
Checking a result
A finite entry can be supported by an explicit walk of that weight, giving an upper bound on the shortest distance. To prove the entry is also a lower bound, the dynamic-programming invariant accounts for every permitted intermediate vertex. Merely finding a short walk is not enough to prove that no shorter walk exists. Conversely, an unreachable entry requires a reachability argument rather than an unsuccessful search through a few candidate paths.
For the three-vertex example, the entry from to has witness of weight . The entry from to has witness of weight . The completed recurrence establishes that no other walk is cheaper. The witnesses help detect arithmetic errors but are not a substitute for the recurrence proof.
Summary
The state restricts internal vertices to the first . A shortest path either avoids internally or splits there. With no negative cycles, the th row and column stay fixed during its stage, permitting the standard in-place cubic algorithm.
Exercises
Quick check
(If , and , what is ?)
Compare the old value with the sum through .
Solution · Answer
It is .
Quick check
(What value represents a pair with no directed walk between it?)
Think of the case with no walk at all.
Solution · Answer
The value is .
Quick check
(Why does a zero-length walk make every initial diagonal entry at most zero?)
Count the walk with no edges.
Solution · Answer
The zero-length walk from a vertex to itself has weight zero; without negative cycles no closed walk has smaller weight, so the diagonal is exactly zero.
Quick check
(Does one negative edge necessarily create a negative cycle?)
Consider a graph with a single edge.
Solution · Answer
No. A graph with a single directed edge of weight and no return path has no cycle at all.