Floyd-Warshall Algorithm

Floyd-Warshall computes shortest paths between all pairs of vertices with a triple loop, in O(V^3) time.

All pairs at once

Floyd-Warshall finds the shortest path between every pair of vertices in a weighted graph. Rather than running a single-source algorithm from each vertex, it builds up the answer with a dynamic-programming recurrence over which intermediate vertices are allowed on a path.

The recurrence

Consider dist[i][j][k], the shortest path from i to j using only the first k vertices as intermediates. Either the best path avoids vertex k, giving dist[i][j][k-1], or it routes through k, giving dist[i][k][k-1] + dist[k][j][k-1]. Taking the minimum and iterating k from 1 to V fills the table. The k dimension can be dropped by updating in place.

• Time: O(V^3)
• Space: O(V^2) with the in-place table
• Handles negative edges (no negative cycles)
• Detects negative cycles via negative diagonal entries

def floyd_warshall(dist):  # dist is a V x V matrix
    V = len(dist)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Reconstructing the paths

To recover the actual routes and not just their lengths, keep a successor table: whenever routing through k improves dist[i][j], record that the path from i now goes through k. Following these entries afterward reconstructs any shortest path in time proportional to its length.

When it wins

The triple loop is trivially simple and has excellent constant factors and a regular memory access pattern, so on small dense graphs Floyd-Warshall often beats running Dijkstra from every vertex, even though both are roughly O(V^3) on dense graphs. On large sparse graphs, repeated Dijkstra or Johnson's algorithm is faster. Floyd-Warshall also computes the transitive closure of a relation by replacing addition and minimum with logical OR and AND, which finds reachability between all pairs.