Floyd-Warshall

Compute the shortest path between every pair of nodes at once — by letting paths route through one more intermediate node each round and relaxing the distance matrix.

Time: O(V³)

Space: O(V²)

All-Pairs Shortest Path

Negative edges: OK

Speed: 900ms

Step 1 of 0Intermediate k = —

Distance matrix — dist[i][j] = shortest i → j so far

j=0

j=1

j=2

j=3

i=0

∞

i=1

∞

i=2

∞

i=3

∞

Reference graph (directed, weighted)

Current Step

Algorithm Details

Time:O(V³)

Space:O(V²)

Technique:Dynamic Prog.

Negative edges:Yes (no neg cycle)

When to Use It

You need shortest paths between all pairs, not one source
Small, dense graphs where V³ is affordable
Graphs with negative edge weights (no negative cycles)
Large sparse graphs — run Dijkstra from each node instead

Knowledge Check

Question 1 of 3

What does Floyd-Warshall compute?

DSAverse

Graph Algorithms

Loading Graph Algorithms...

BFS Traversal

visited: 0 / 7