Computing All-Pairs Distances With Floyd-Warshall

From Edge Weights to All-Pairs Distances

When a directed weighted graph has only a few vertices, it is possible to compute shortest distances one source at a time. Floyd–Warshall organizes the same task into a sequence of matrix updates: at stage $k$, it asks whether allowing vertex $k$ as an intermediate point improves any current distance. Keeping the whole matrix visible at every stage makes the calculation systematic and helps reveal exactly which routes produce improvements.

Throughout, graphs are finite and simple, and the examples are directed weighted graphs. A directed edge from $i$ to $j$ has a specified weight. A directed path follows edge directions, and its weight is the sum of its edge weights. The distance from $i$ to $j$ is the minimum weight of a directed path from $i$ to $j$, when such a minimum exists. If there is no path, the distance is $\infty$. The distance from a vertex to itself is initialized as $0$.

Definition: Number the vertices $1,\dots,n$. Let $D^{(k)}_{ij}$ denote the best distance currently recorded from $i$ to $j$ when only vertices $1,\dots,k$ may occur as internal vertices of a route. The initial matrix $D^{(0)}$ has $D^{(0)}_{ii}=0$, $D^{(0)}_{ij}$ equal to the weight of edge $ij$ when that edge exists, and $D^{(0)}_{ij}=\infty$ otherwise. Floyd–Warshall updates by $$ D^{(k)}_{ij}=\min\left(D^{(k-1)}_{ij},\ D^{(k-1)}_{ik}+D^{(k-1)}_{kj}\right). $$ Here $+\infty=\infty$.

The first term in the minimum keeps the best route that avoids using $k$ internally. The second tests a route from $i$ to $j$ that goes through $k$, using the best recorded $i$-to-$k$ and $k$-to-$j$ routes from the preceding stage. Use the same vertex order for both the rows and columns at every stage. If $D^{(k-1)}_{ik}$ or $D^{(k-1)}_{kj}$ is $\infty$, that candidate route cannot improve a finite entry.

Why the Stage Update Works

Theorem: If the directed weighted graph has no negative-weight directed cycle, then after stage $k$, each entry $D^{(k)}_{ij}$ is the shortest distance from $i$ to $j$ among routes whose internal vertices belong to $\{1,\dots,k\}$. In particular, $D^{(n)}$ gives all-pairs shortest distances.

Proof. For $k=0$, a route with no internal vertices is either the empty route from a vertex to itself, of weight $0$, or a single edge. If no such edge exists, there is no route of this form. Thus $D^{(0)}$ records exactly the best weights allowed at this stage.

Suppose the claim holds for stage $k-1$. Consider a shortest route from $i$ to $j$ whose internal vertices are in $\{1,\dots,k\}$. Because there is no negative-weight directed cycle, any repeated-vertex portion of a route has nonnegative weight and can be removed without increasing its weight. Thus a minimum can be attained by a route with no repeated vertices. If that route does not use $k$ internally, its weight is at least $D^{(k-1)}_{ij}$, and the best such route is recorded by that entry. If it does use $k$ internally, it uses $k$ only once; split it at $k$. Its two parts have internal vertices only in $\{1,\dots,k-1\}$, so their best possible weights are $D^{(k-1)}_{ik}$ and $D^{(k-1)}_{kj}$. The best route of this second type therefore has weight $D^{(k-1)}_{ik}+D^{(k-1)}_{kj}$. Taking the minimum of these two cases gives the stated recurrence and proves the claim at stage $k$. Induction proves it for every stage, including $k=n$. $\square$

If the graph has a negative-weight directed cycle, a shortest distance may fail to exist: following that cycle repeatedly makes route weights arbitrarily small. A negative diagonal entry in the final matrix signals such a cycle. The examples below have no negative-weight directed cycle, so their final entries are well-defined shortest distances.

A Four-Vertex Calculation, Stage by Stage

Worked Example: Negative Edge Weights Without a Negative Cycle

Let the directed weighted graph have vertex set $V=\{A,B,C,D\}$ and edge set $E=\{(A,B,4),(A,C,10),(B,C,-2),(B,D,7),(C,D,3),(D,A,2)\}$, where each triple gives a directed edge and its weight. Use the vertex order $A,B,C,D$. The directed cycles have weights $7$ for $A\to B\to C\to D\to A$, $13$ for $A\to B\to D\to A$, and $15$ for $A\to C\to D\to A$; all are positive. So the graph has no negative-weight directed cycle.

Initially, diagonal entries are $0$, edge entries equal their weights, and absent edges have weight $\infty$. Thus:

D^{(0)}= \begin{pmatrix} 0&4&10&\infty\\ \infty&0&-2&7\\ \infty&\infty&0&3\\ 2&\infty&\infty&0 \end{pmatrix}.

Stage $A$. Compare each entry with the candidate $D^{(0)}_{iA}+D^{(0)}_{Aj}$. For row $D$, the candidate to $B$ is $2+4=6$, improving on $\infty$. The candidate to $C$ is $2+10=12$, improving on $\infty$. Other finite candidates do not improve their entries; for instance $D\to A\to A$ has weight $2+0=2$, the existing value. The resulting matrix is

D^{(A)}= \begin{pmatrix} 0&4&10&\infty\\ \infty&0&-2&7\\ \infty&\infty&0&3\\ 2&6&12&0 \end{pmatrix}.

Stage $B$. The new improving candidates are $A\to C$ via $B$, with weight $4+(-2)=2$ instead of $10$; $A\to D$ via $B$, with weight $4+7=11$ instead of $\infty$; and $D\to C$ via $B$, with weight $6+(-2)=4$ instead of $12$. No other candidate is smaller than its current entry. Therefore

D^{(B)}= \begin{pmatrix} 0&4&2&11\\ \infty&0&-2&7\\ \infty&\infty&0&3\\ 2&6&4&0 \end{pmatrix}.

Stage $C$. Going through $C$ improves $A\to D$: the candidate is $D^{(B)}_{AC}+D^{(B)}_{CD}=2+3=5$, smaller than $11$. It also improves $B\to D$: the candidate is $-2+3=1$, smaller than $7$. For example, the candidate for $D\to D$ is $4+3=7$, which does not improve the existing $0$. The matrix is

D^{(C)}= \begin{pmatrix} 0&4&2&5\\ \infty&0&-2&1\\ \infty&\infty&0&3\\ 2&6&4&0 \end{pmatrix}.

Stage $D$. The entries that improve are $B\to A$, with candidate $1+2=3$; $C\to A$, with candidate $3+2=5$; and $C\to B$, with candidate $3+6=9$. For the remaining entries, going through $D$ does not give a smaller value. For instance, $A\to B$ has candidate $5+6=11$, which is larger than $4$, and $A\to C$ has candidate $5+4=9$, which is larger than $2$. The final matrix is

D^{(D)}= \begin{pmatrix} 0&4&2&5\\ 3&0&-2&1\\ 5&9&0&3\\ 2&6&4&0 \end{pmatrix}.

Check: The entry $D^{(D)}_{AD}=5$ is attained by $A\to B\to C\to D$, with weight $4+(-2)+3=5$. A shorter route would have to improve this entry in a later stage, but all four vertices have already been allowed; the displayed stage-by-stage recurrence tests every possible last intermediate vertex. Also, $D^{(D)}_{BA}=3$ is attained by $B\to D\to A$, with weight $7+2=9$, or by $B\to C\to D\to A$, with weight $(-2)+3+2=3$. This verifies the final entry using the actual route weights.

Unreachable Vertices and Indirect Routes

Worked Example: An Unreachable Pair

Let $V=\{1,2,3\}$ and $E=\{(1,2,5),(1,3,20),(2,3,-1)\}$, with vertex order $1,2,3$. This directed acyclic graph has no directed cycle, and vertex $3$ has no outgoing edges. Its initial matrix is

D^{(0)}= \begin{pmatrix} 0&5&20\\ \infty&0&-1\\ \infty&\infty&0 \end{pmatrix}.

At stage $1$, no entry improves. In particular, the only finite distance into $1$ is $D^{(0)}_{11}=0$, so going through $1$ simply tests routes already recorded. Thus $D^{(1)}=D^{(0)}$.

At stage $2$, the candidate for $1\to3$ is $D^{(1)}_{12}+D^{(1)}_{23}=5+(-1)=4$, which improves on $20$. Other entries do not improve: for example, $1\to2$ has candidate $5+0=5$, equal to its existing value, and $2\to3$ has candidate $0+(-1)=-1$, also equal to its existing value. Hence

D^{(2)}= \begin{pmatrix} 0&5&4\\ \infty&0&-1\\ \infty&\infty&0 \end{pmatrix}.

At stage $3$, no entry improves. A route through $3$ cannot continue to another vertex, since $3$ has no outgoing edge; the diagonal entry $D^{(2)}_{33}=0$ does not change any other candidate. Therefore $D^{(3)}=D^{(2)}$.

Check: From $1$ to $3$, the available routes are the direct edge of weight $20$ and the route $1\to2\to3$ of weight $5+(-1)=4$, so the final value is $4$. There is no directed route from $3$ to $1$, so the corresponding entry remains $\infty$. An infinite entry is not a very large distance; it means no directed path exists.

Zero-Weight Edges and Isolated Vertices

Worked Example: A Zero-Weight Edge and an Isolated Vertex

Let $V=\{1,2,3,4\}$ and $E=\{(1,2,0),(2,3,2),(1,3,5)\}$, ordered $1,2,3,4$. Vertex $4$ is isolated, meaning it has no incident directed edges. The graph is acyclic, so it has no negative-weight directed cycle. The initial matrix is

D^{(0)}= \begin{pmatrix} 0&0&5&\infty\\ \infty&0&2&\infty\\ \infty&\infty&0&\infty\\ \infty&\infty&\infty&0 \end{pmatrix}.

At stage $1$, the only outgoing edge from $1$ is $1\to2$ of weight $0$; the candidates through $1$ do not improve any entry. So $D^{(1)}=D^{(0)}$. At stage $2$, the candidate for $1\to3$ is $D^{(1)}_{12}+D^{(1)}_{23}=0+2=2$, improving on $5$. All entries involving $4$ and a different vertex remain infinite: no route can enter or leave the isolated vertex. Thus

D^{(2)}= \begin{pmatrix} 0&0&2&\infty\\ \infty&0&2&\infty\\ \infty&\infty&0&\infty\\ \infty&\infty&\infty&0 \end{pmatrix}.

At stage $3$, vertex $3$ has no outgoing edge, so it creates no improved route. At stage $4$, vertex $4$ is isolated, so it also creates no improved route. Consequently, $D^{(3)}=D^{(4)}=D^{(2)}$.

Check: The two directed routes from $1$ to $3$ are the direct edge of weight $5$ and the route through $2$ of weight $0+2=2$. Their minimum is $2$, as recorded. The zero-weight edge is a genuine edge, not an absent edge: $D^{(4)}_{12}=0$, whereas $D^{(4)}_{21}=\infty$.

Reading and Checking the Final Matrix

After the last stage, the row index is the starting vertex and the column index is the destination. Thus $D^{(n)}_{ij}$ answers the directed distance question from $i$ to $j$; in general, $D^{(n)}_{ij}$ need not equal $D^{(n)}_{ji}$. The diagonal should be $0$ when there is no negative cycle. If any diagonal entry is negative, the graph contains a negative-weight directed cycle and at least some shortest-distance questions have no finite answer.

A practical hand calculation can be organized as follows: copy the previous matrix, choose the current intermediate vertex $k$, and check each pair $(i,j)$ using the candidate $D_{ik}+D_{kj}$. Write down only the entries that decrease or change from $\infty$, then display the full updated matrix. When checking a finite result, name a route whose edge weights sum to that entry. When checking an infinite result, verify that no directed route connects the pair.

Common mistake: treating a direct edge as the final answer. In the second example, the direct edge $1\to3$ has weight $20$. Keeping $20$ in the final matrix because it is the listed edge weight is wrong: the route $1\to2\to3$ has weight $5+(-1)=4$. The correction is to apply the stage-$2$ comparison, $\min(20,5+(-1))=\min(20,4)=4$. Another common error is to replace $\infty$ by an arbitrary large number and then add it; keep $\infty$ symbolic so that unreachable pairs remain unambiguous.

Check Your Understanding

For each question, identify the directed route or stage update that supports your answer.

In the first example, which stage first changes the entry from $A$ to $D$, and what candidate route gives the new value?
Why does an entry $D^{(k)}_{ij}=\infty$ not mean that the distance is merely large?
For a graph with no negative-weight directed cycle, what does a negative final diagonal entry imply?
In the third example, why does the zero-weight edge $1\to2$ not imply that $D_{21}=0$?
At stage $k$, what are the two types of routes compared by the Floyd–Warshall recurrence?