Engineering Notes

Floyd-Warshall Shortest Path

2 min read

Algorithm 97 (Shortest Path) / Floyd-Warshall Algorithm

Citation: Floyd, R. W. (1962). Algorithm 97: Shortest Path. Communications of the ACM, 5(6), 345.

Core Contribution

Published the Floyd-Warshall algorithm for finding shortest paths in weighted graphs. Also established the invariant assertion method for proving correctness of programs — proving that the algorithm maintains a loop invariant rather than trying to prove the final result directly.

Key Concepts

  1. Dynamic programming: Break problem into overlapping subproblems
  2. Path matrix: dp[k][i][j] = shortest path from i to j using only vertices 0..k
  3. Loop invariant: At each iteration k, dp[i][j] = shortest path using vertices in {0..k}
  4. Transitive closure: Extends to reachability problems

Invariant Assertion Method

Floyd’s paper established the pattern of:

  1. Define the loop invariant
  2. Prove invariant holds initially (base case)
  3. Prove invariant preserved by loop body
  4. Use invariant to prove correctness after loop

This is now standard for proving algorithm correctness.

Time Complexity

  • O(V³) where V = number of vertices
  • Worse than Dijkstra for single-source (O(E log V)) on sparse graphs
  • Better than repeated Dijkstra for all-pairs shortest path on dense graphs

Floyd-Warshall Code

def floyd_warshall(graph):
    dist = graph.copy()  # adjacency matrix
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

See Also

Graph View