Floyd-Warshall Algorithm

1. Introduction

The Floyd-Warshall algorithm, independently discovered by Robert Floyd (1962) and Stephen Warshall (1962), solves the all-pairs shortest path problem. Given a weighted directed graph, it computes the shortest path distances between every pair of vertices simultaneously. This stands in contrast to single-source algorithms like Dijkstra's or Bellman-Ford, which must be run once per source vertex.

The algorithm is based on dynamic programming and uses an elegant formulation: it considers whether routing a path through an intermediate vertex k produces a shorter path than the current best known path. By systematically considering all possible intermediate vertices, the algorithm builds up optimal solutions from smaller subproblems.

"The Floyd-Warshall algorithm exemplifies how dynamic programming can elegantly solve complex optimization problems through a simple recurrence relation." -- Robert Sedgewick, Algorithms

2. How It Works

The algorithm maintains a distance matrix dist[i][j] that stores the shortest known distance from vertex i to vertex j. It iterates through all vertices as potential intermediate points on paths.

Dynamic Programming Recurrence

Let dist_k[i][j] denote the shortest path from i to j using only vertices {1, 2, ..., k} as intermediate vertices. The recurrence is:

dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j])

This captures two possibilities: either the shortest path from i to j does not pass through vertex k (first term), or it does pass through k (second term, which is the sum of the shortest path from i to k and from k to j).

High-Level Steps

1. Initialize: Set dist[i][j] to the direct edge weight if an edge exists, 0 for i = j, and infinity otherwise. Initialize the next-hop matrix for path reconstruction.
2. Iterate over intermediates: For each vertex k from 1 to V, check whether routing through k improves the shortest path between every pair (i, j).
3. Detect negative cycles: After completion, if any diagonal element dist[i][i] is negative, a negative-weight cycle exists through vertex i.

3. Algorithm and Pseudocode

functionFloydWarshall(Graph): let V = number of vertices let dist[V][V] = INFINITY let next[V][V] = NULL // Step 1: Initialize with direct edgesfor each vertex v: dist[v][v] = 0for each edge (u, v, w): dist[u][v] = w next[u][v] = v // Step 2: Consider each vertex as intermediatefor k = 1to V: for i = 1to V: for j = 1to V: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] next[i][j] = next[i][k] // Step 3: Detect negative cyclesfor i = 1to V: if dist[i][i] < 0: return"Negative cycle detected"return dist[][], next[][]

Path Reconstruction

functionReconstructPath(next, u, v): if next[u][v] == NULL: return"No path exists" path = [u] while u != v: u = next[u][v] path.append(u) return path

4. Complexity Analysis

The O(V^3) time complexity is the same regardless of the number of edges. This makes Floyd-Warshall particularly efficient for dense graphs where running Dijkstra's algorithm from each vertex would yield O(V * (V + E) log V), which for dense graphs is O(V^3 log V).

5. Worked Example

Consider a directed graph with 4 vertices (1, 2, 3, 4):

Initial Distance Matrix

k = 1 (using vertex 1 as intermediate)

Check all pairs (i,j) to see if going through vertex 1 improves the distance:

• dist[4][2]: via 1: dist[4][1] + dist[1][2] = 7 + 3 = 10 < inf. Update to 10.
• dist[4][3]: via 1: dist[4][1] + dist[1][3] = 7 + 8 = 15 < inf. Update to 15.

k = 2 (using vertex 2 as intermediate)

• dist[1][3]: via 2: dist[1][2] + dist[2][3] = 3 + 2 = 5 < 8. Update to 5.
• dist[1][4]: via 2: dist[1][2] + dist[2][4] = 3 + 10 = 13 < inf. Update to 13.
• dist[4][3]: via 2: dist[4][2] + dist[2][3] = 10 + 2 = 12 < 15. Update to 12.
• dist[4][4]: via 2: dist[4][2] + dist[2][4] = 10 + 10 = 20 (no improvement).

k = 3 (using vertex 3 as intermediate)

• dist[1][4]: via 3: dist[1][3] + dist[3][4] = 5 + 1 = 6 < 13. Update to 6.
• dist[2][4]: via 3: dist[2][3] + dist[3][4] = 2 + 1 = 3 < 10. Update to 3.
• dist[4][4]: via 3: dist[4][3] + dist[3][4] = 12 + 1 = 13 (no improvement over 0).

k = 4 (using vertex 4 as intermediate)

• dist[1][1]: via 4: dist[1][4] + dist[4][1] = 6 + 7 = 13 (no improvement over 0).
• dist[2][1]: via 4: dist[2][4] + dist[4][1] = 3 + 7 = 10 < inf. Update to 10.
• dist[3][1]: via 4: dist[3][4] + dist[4][1] = 1 + 7 = 8 < inf. Update to 8.
• dist[3][2]: via 4: dist[3][4] + dist[4][2] = 1 + 10 = 11 < inf. Update to 11.

Final Distance Matrix

No diagonal element is negative, confirming there are no negative-weight cycles.

6. Path Reconstruction

The next matrix stores, for each pair (i, j), the first vertex on the shortest path from i to j. By repeatedly looking up the next vertex, the full path can be reconstructed in O(V) time.

Example: Path from 1 to 4

• next[1][4] = 2 (go to vertex 2 first)
• next[2][4] = 3 (go to vertex 3)
• next[3][4] = 4 (arrive at vertex 4)

Reconstructed path: 1 -> 2 -> 3 -> 4 with total distance 6.

7. Advantages and Disadvantages

Advantages

• All-pairs solution: Computes shortest paths between every pair of vertices in a single execution.
• Handles negative weights: Correctly processes graphs with negative edge weights.
• Simplicity: The algorithm consists of three nested loops and is very easy to implement.
• Negative cycle detection: Negative cycles are indicated by negative values on the diagonal of the distance matrix.
• Path reconstruction: The next-hop matrix enables efficient reconstruction of any shortest path.

Disadvantages

• Cubic time complexity:O(V^3) makes it impractical for very large graphs.
• Quadratic space: Requires O(V^2) memory for the distance and next-hop matrices.
• Inefficient for sparse graphs: For sparse graphs with few edges, running Dijkstra's algorithm from each vertex is faster.
• Overkill for single-source: If only shortest paths from one source are needed, single-source algorithms are more efficient.

8. Comparison with Other Algorithms

9. Applications

• Network analysis: Computing the diameter (longest shortest path) and center of a network.
• Transitive closure: Determining reachability between all pairs of vertices in a directed graph.
• Optimal routing: Pre-computing routing tables for small to medium-sized networks where all-pairs information is needed.
• Shortest path in games: Computing movement costs between all locations on small game maps.
• Detecting arbitrage: Similar to Bellman-Ford, the all-pairs version can find arbitrage opportunities across all currency pairs simultaneously.
• Minimum weight cycle: Finding the minimum weight cycle in a graph by checking the diagonal after execution.

10. References

1. Floyd, R. W. (1962). "Algorithm 97: Shortest Path." Communications of the ACM, 5(6), 345.
2. Warshall, S. (1962). "A Theorem on Boolean Matrices." Journal of the ACM, 9(1), 11-12.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 25.
4. Sedgewick, R. and Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Section 4.4.
5. Kleinberg, J. and Tardos, E. (2005). Algorithm Design. Addison-Wesley. Chapter 6.