Floyd-Warshall (All-Pairs Shortest Paths)
DSA · Graphs
Theory
Floyd-Warshall finds the shortest distance between every pair of vertices in a weighted graph. It uses dynamic programming: dist[i][j] starts as the direct edge weight (or infinity), and the algorithm then tries every vertex k as an intermediate stop, updating dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After considering all k, the table contains the shortest path for every pair. It works with negative edge weights as long as there is no negative cycle, and a negative value on the diagonal (dist[i][i] < 0) reveals such a cycle. With three nested loops it runs in O(V^3), so it suits graphs with up to a few hundred vertices.
Why we use it
When you need distances between all pairs, running Dijkstra from every vertex is more code and, on dense graphs, no faster. Floyd-Warshall is short, handles negative weights and detects negative cycles.
When to use it
Use it for small or dense graphs when all-pairs distances are needed, such as a distance table between cities or transitive closure. Use Dijkstra for one source on large sparse graphs.
How it works
- dist = adjacency matrix
- For each intermediate k
- For each pair (i, j)
- dist[i][k] + dist[k][j] < dist[i][j]? Yes: Update dist[i][j]. No: Keep.
- All-pairs shortest paths in O(V^3)
Syntax
for k in V:
for i in V:
for j in V:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Time O(V^3) Space O(V^2)Example
INF = float("inf")
cities = ["Delhi", "Jaipur", "Agra", "Lucknow"]
# adjacency matrix of road distances (km); INF = no direct road
dist = [
[0, 280, 230, INF],
[280, 0, 240, INF],
[230, 240, 0, 335],
[INF, INF, 335, 0],
]
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]
print(f"{'':8}" + "".join(f"{c:>9}" for c in cities))
for i, row in enumerate(dist):
print(f"{cities[i]:8}" + "".join(f"{d:>9}" for d in row))
print("Negative cycle?", any(dist[i][i] < 0 for i in range(n)))Key points
- Dynamic programming over intermediate vertices k
- O(V^3) time, O(V^2) memory
- Handles negative edges; detects negative cycles on the diagonal
- Best for small or dense graphs