Reconstructing Paths From Floyd-Warshall Tables

From Distances to Routes

Floyd–Warshall computes the shortest distance between every ordered pair of vertices, but a distance alone does not say which edges form a route attaining it. To recover routes, the algorithm can maintain a small amount of additional information whenever it improves a distance. This tutorial develops next-hop and predecessor tables, explains how to use them, and makes explicit what to do when a pair is unreachable.

Throughout, \(G=(V,E)\) is a finite directed graph with no loops or multiple edges. Each edge \(uv\) has a real weight \(w(u,v)\); weights may be negative. Assume that \(G\) has no negative-weight cycle. A path is a sequence of distinct vertices with a directed edge between each consecutive pair; its weight is the sum of those edge weights. The shortest-path distance \(D[i,j]\) is the minimum weight of a path from \(i\) to \(j\), and is \(\infty\) if there is no such path. The empty path from a vertex to itself has weight zero, so \(D[i,i]=0\).

The no-negative-cycle assumption ensures that every reachable pair has a finite minimum: if a route repeats a vertex, the portion between repetitions is a cycle of nonnegative weight, which can be removed without increasing the route's weight. Repeating this removal gives a path, and there are only finitely many paths in a finite graph. If a negative cycle is present, distances for pairs that can reach and leave that cycle need separate treatment; the route-reconstruction rules below assume no such cycle.

Adding Route Data to Floyd–Warshall

Use the usual Floyd–Warshall vertex order \(1,\ldots,n\). Initialize \(D[i,i]=0\), and set \(D[i,j]=w(i,j)\) for each directed edge \(ij\); set \(D[i,j]=\infty\) when there is no edge and \(i\ne j\). Set \(N[i,j]=j\) for a direct edge \(ij\), and NIL for all other entries. The corresponding direct-edge predecessor is \(P[i,j]=i\); other predecessor entries are NIL.

At the stage that allows vertex \(k\) as an intermediate vertex, compare the current distance with the route through \(k\). If that route strictly improves the distance, update the distance and route data together:

The next hop is inherited from the first part, \(i\) to \(k\); the predecessor of \(j\) is inherited from the second part, \(k\) to \(j\). If the two distances are equal, keep the existing route data. This strict-improvement rule avoids replacing a route merely because another route ties it. In particular, it does not add unnecessary zero-weight cycles to an already optimal route. Under the no-negative-cycle assumption, an improving candidate cannot require a missing next hop or predecessor: a candidate using a diagonal empty segment cannot strictly improve a distance.

Proof. Initially, each finite off-diagonal entry is a direct edge, and its next hop and predecessor are exactly its endpoint data. Each diagonal entry describes the empty path and has no route pointer. Suppose the invariant holds before processing \(k\). A route allowed after this stage either does not use \(k\) as an intermediate vertex, or can be split at \(k\) into a route from \(i\) to \(k\) and one from \(k\) to \(j\). The best candidate of the second kind has weight \(D[i,k]+D[k,j]\), so comparing it with the old \(D[i,j]\) gives the Floyd–Warshall update. If it is strictly better, its first edge is the first edge of the selected \(i\)-to-\(k\) route, and its last edge is the last edge of the selected \(k\)-to-\(j\) route. Thus the stated next-hop and predecessor updates describe the improved route. If it does not improve, retaining the old route data preserves the invariant. This proves the claim at every stage by induction. In the final table, a selected shortest route has shortest subroutes: replacing a subroute by a strictly better one would produce a route of smaller total weight. Therefore the next-hop pointer at each vertex leads along a selected shortest route to the destination; the predecessor pointer gives the same route in reverse. Since a shortest route can be chosen to be a path, reconstruction reaches its destination without repeating vertices. \(\square\)

For equal-weight alternatives, the rule above selects whichever route was recorded first. If a particular tie-breaking policy is wanted, apply it consistently, for example by storing the number of edges and preferring fewer edges when distances tie. The selected route may differ, but its distance remains the shortest distance.

Reconstructing and Reporting Routes

For a reachable pair \(s\ne t\), start at \(s\), append \(N[s,t]\), then look up the next hop for the new current vertex and the same destination \(t\). Continue until reaching \(t\). For \(s=t\), return the single-vertex route \(s\). If \(D[s,t]=\infty\), report that no directed route exists; do not try to follow pointers. With predecessor data, start at \(t\), repeatedly replace the current vertex \(v\) by \(P[s,v]\), and reverse the resulting list at the end.

Proof. If a directed path exists, it has finitely many edges and hence finite weight. Its minimum-weight path therefore has finite distance, so \(D[s,t]\ne\infty\). Conversely, a finite distance can only be initialized from an edge or obtained by concatenating two finite distances. Inductively, each finite entry represents a route. Thus a finite final entry implies a path exists. If \(s=t\), the empty path gives distance zero, so the diagonal is not an unreachable pair. \(\square\)

Common Mistakes

A frequent error is to update \(D[i,j]\) but forget to update its route pointer. That leaves a distance from the improved route and a pointer from the old route, so following the table may return a route whose weight does not equal \(D[i,j]\). In the first example, after improving \(D[1,3]\) from \(10\) to \(6\) through vertex \(2\), retaining \(N[1,3]=3\) would incorrectly claim that the first step on the selected route is \(1\to3\), whose weight is \(10\). The correction is to update \(N[1,3]\) to \(N[1,2]=2\) at the same time as the distance.

Another mistake is to treat \(\infty\) as an ordinary number and attempt route reconstruction anyway. An unreachable pair has no first edge to follow. Check whether \(D[s,t]\) is finite before consulting the route table. Also keep the direction of predecessor reconstruction straight: predecessors are followed from the destination back to the source, and the resulting vertex list must be reversed.

Route tables matter whenever the desired output is an actual itinerary, communication route, or sequence of transitions rather than just its cost. Maintaining the pointer during the distance computation avoids searching the graph again for each requested pair. The essential consistency check is that the reconstructed route uses directed edges and that the sum of their weights equals the table entry.