Floyd–Warshall algorithm

Lore & Background

The Floyd–Warshall algorithm is an example of dynamic programming. The algorithm compares many possible paths through the graph between each pair of vertices. It is guaranteed to find all shortest paths and does so with Θ(|V|³) comparisons, even though there may be Θ(|V|²) edges. It works by incrementally improving an estimate on the shortest path between two vertices until the estimate is optimal. The algorithm uses a recursive formula: shortestPath(i,j,k) = min(shortestPath(i,j,k-1), shortestPath(i,k,k-1) + shortestPath(k,j,k-1)), with the base case shortestPath(i,j,0) = w(i,j).

Reader's Guide

The Floyd–Warshall algorithm is significant as a foundational dynamic programming solution for the all-pairs shortest path problem. Its ability to handle positive or negative edge weights (without negative cycles) makes it versatile, though its Θ(|V|³) time complexity limits it to graphs of moderate size. Beyond shortest paths, the algorithm's variants serve other purposes: finding transitive closure of a relation and, in connection with the Schulze voting system, computing widest paths between all pairs of vertices. Its legacy lies in its simplicity, elegance, and broad applicability across graph theory, network analysis, and voting systems.

Did You Know?

• The algorithm is also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm.