Floyd-Warshall Algorithm

Master the all-pairs shortest path algorithm using dynamic programming with three nested loops, path reconstruction, and practical applications.

The Problem

What if you need shortest paths between ALL pairs of vertices, not just from one source? You could run Dijkstra V times, but Floyd-Warshall solves this elegantly with a single dynamic programming approach using three nested loops.

The Key Insight

Floyd-Warshall asks a brilliant question: "What is the shortest path from i to j using only vertices {0, 1, ..., k} as intermediate stops?"

Call this dp[k][i][j]. The recurrence is:

Either the shortest path from i to j using intermediates {0..k} does NOT go through k: dp[k][i][j] = dp[k-1][i][j]
Or it DOES go through k: dp[k][i][j] = dp[k-1][i][k] + dp[k-1][k][j]
Take the minimum: dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

Since we only ever look at the previous layer (k-1), we can optimize to a 2D table updated in-place.

Algorithm (Simplified)

For k = 0 to V-1	// Try each vertex as intermediate
For i = 0 to V-1	// For each source
For j = 0 to V-1	// For each destination

That is it. Three nested loops. The order matters: k MUST be the outermost loop.

Dry Run Example

Graph

0 --(3)--> 1

| ^|

(8) (2)|(-4)

| / v

+--> 2 <--(7)-- 1

Edges: (0,1,3), (0,2,8), (1,2,-4), (2,1,2)

Initial distance matrix

0 1 2

0 [ 0, 3, 8 ]

1 [ inf, 0, -4 ]

2 [ inf, 2, 0 ]

k=0 (using vertex 0 as intermediate):

dist[1][2] = min(-4, inf+8) = -4 (no change)

dist[2][1] = min(2, inf+3) = 2 (no change)

No improvements through vertex 0.

k=1 (using vertex 1 as intermediate):

dist[0][2] = min(8, 3+(-4)) = min(8, -1) = -1 ← improved!

dist[2][0] = min(inf, 2+inf) = inf (no change)

0 1 2

0 [ 0, 3, -1 ]

1 [ inf, 0, -4 ]

2 [ inf, 2, 0 ]

k=2 (using vertex 2 as intermediate):

dist[0][1] = min(3, -1+2) = min(3, 1) = 1 ← improved!

dist[1][0] = min(inf, -4+inf) = inf (no change)

Final

0 1 2

0 [ 0, 1, -1 ]

1 [ inf, 0, -4 ]

2 [ inf, 2, 0 ]

Python Implementation

Example

def floyd_warshall(graph_matrix): """ graph_matrix: V x V matrix where graph_matrix[i][j] = weight of edge i→j Use float('inf') for no edge, 0 for diagonal. Returns: (shortest distance matrix, next-hop matrix for path reconstruction) """ V = len(graph_matrix) dist = [row[:] for row in graph_matrix] # Deep copy # For path reconstruction: next[i][j] = next vertex after i on path to j nxt = [[None] * V for _ in range(V)] for i in range(V): for j in range(V): if dist[i][j] != float('inf') and i != j: nxt[i][j] = j # Main algorithm 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] nxt[i][j] = nxt[i][k] # Negative cycle detection: if dist[i][i] < 0 for i in range(V): if dist[i][i] < 0: raise ValueError(f"Negative cycle involving vertex {i}") return dist, nxt def reconstruct_path(nxt, u, v): """Reconstruct shortest path from u to v.""" if nxt[u][v] is None: return [] path = [u] while u != v: u = nxt[u][v] path.append(u) return path # Example INF = float('inf') graph = [ [0, 3, 8], [INF, 0, -4], [INF, 2, 0] ] dist, nxt = floyd_warshall(graph) print(dist[0]) # [0, 1, -1] print(reconstruct_path(nxt, 0, 2)) # [0, 1, 2]

C++ Implementation

Example

#include <vector> #include <climits> using namespace std; const int INF = 1e9; void floydWarshall(vector<vector<int>>& dist) { int V = dist.size(); for (int k = 0; k < V; k++) for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) if (dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); }

Time and Space Complexity

Time: O(V³) — three nested loops each iterating V times
Space: O(V²) — for the distance matrix (in-place modification)

When to Use Floyd-Warshall

Small graphs (V ≤ 400-500 typically) where you need all-pairs distances
Graphs with negative edges (but no negative cycles)
When you need transitive closure (reachability between all pairs)
Dense graphs (where running Dijkstra V times would be similar cost)

For large sparse graphs, running Dijkstra from each vertex O(V(V+E) log V) is often faster.

Applications

All-pairs shortest paths in small networks: City-to-city distances in a region
Transitive closure: Can vertex i reach vertex j? (set weights to 1, use OR instead of min)
Detecting negative cycles: If dist[i][i] < 0 after algorithm runs
Minimax/maximin paths: Replace min with max or + with min for different optimization criteria
Graph diameter: The longest shortest path between any pair of vertices

The Problem

The Key Insight

Floyd-Warshall asks a brilliant question: "What is the shortest path from i to j using only vertices {0, 1, ..., k} as intermediate stops?"

Call this dp[k][i][j]. The recurrence is:

Either the shortest path from i to j using intermediates {0..k} does NOT go through k: dp[k][i][j] = dp[k-1][i][j]
Or it DOES go through k: dp[k][i][j] = dp[k-1][i][k] + dp[k-1][k][j]
Take the minimum: dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

Since we only ever look at the previous layer (k-1), we can optimize to a 2D table updated in-place.

Algorithm (Simplified)

For k = 0 to V-1	// Try each vertex as intermediate
For i = 0 to V-1	// For each source
For j = 0 to V-1	// For each destination

That is it. Three nested loops. The order matters: k MUST be the outermost loop.

Dry Run Example

Graph

0 --(3)--> 1

| ^|

(8) (2)|(-4)

| / v

+--> 2 <--(7)-- 1

Edges: (0,1,3), (0,2,8), (1,2,-4), (2,1,2)

Initial distance matrix

0 1 2

0 [ 0, 3, 8 ]

1 [ inf, 0, -4 ]

2 [ inf, 2, 0 ]

k=0 (using vertex 0 as intermediate):

dist[1][2] = min(-4, inf+8) = -4 (no change)

dist[2][1] = min(2, inf+3) = 2 (no change)

No improvements through vertex 0.

k=1 (using vertex 1 as intermediate):

dist[0][2] = min(8, 3+(-4)) = min(8, -1) = -1 ← improved!

dist[2][0] = min(inf, 2+inf) = inf (no change)

0 1 2

0 [ 0, 3, -1 ]

1 [ inf, 0, -4 ]

2 [ inf, 2, 0 ]

k=2 (using vertex 2 as intermediate):

dist[0][1] = min(3, -1+2) = min(3, 1) = 1 ← improved!

dist[1][0] = min(inf, -4+inf) = inf (no change)

Final

0 1 2

0 [ 0, 1, -1 ]

1 [ inf, 0, -4 ]

2 [ inf, 2, 0 ]

Python Implementation

Example

C++ Implementation

Example

Time and Space Complexity

Time: O(V³) — three nested loops each iterating V times
Space: O(V²) — for the distance matrix (in-place modification)

When to Use Floyd-Warshall

Small graphs (V ≤ 400-500 typically) where you need all-pairs distances
Graphs with negative edges (but no negative cycles)
When you need transitive closure (reachability between all pairs)
Dense graphs (where running Dijkstra V times would be similar cost)

For large sparse graphs, running Dijkstra from each vertex O(V(V+E) log V) is often faster.

Applications

All-pairs shortest paths in small networks: City-to-city distances in a region
Transitive closure: Can vertex i reach vertex j? (set weights to 1, use OR instead of min)
Detecting negative cycles: If dist[i][i] < 0 after algorithm runs
Minimax/maximin paths: Replace min with max or + with min for different optimization criteria
Graph diameter: The longest shortest path between any pair of vertices

Floyd-Warshall Algorithm

The Problem

The Key Insight

Algorithm (Simplified)

Dry Run Example

Graph

Initial distance matrix

Final

Python Implementation

C++ Implementation

Time and Space Complexity

When to Use Floyd-Warshall

Applications

Continue learning this concept

Floyd-Warshall Algorithm

The Problem

The Key Insight

Algorithm (Simplified)

Dry Run Example

Graph

Initial distance matrix

Final

Python Implementation

C++ Implementation

Time and Space Complexity

When to Use Floyd-Warshall

Applications

Continue learning this concept