Floyd–Warshall Algorithm
Floyd Warshall is a GFG problem (Medium). You are given a weighted directed graph with n vertices as an n × n matrix dist:
dist[i][j]is the weight of the edge fromitoj;dist[i][i]is 0;10^8means there is no edge fromitoj.
Update the matrix in place so that dist[i][j] becomes the shortest distance from every vertex i to every vertex j, keeping 10^8 where j cannot be reached from i. Edge weights may be negative, but the graph has no negative cycle.
With n at most 100, an O(n³) pass over every triple of vertices is about a million steps, which is fast enough.
- 1 <= V <= 100
- -1000 <= weight <= 1000
- V³ time makes this practical only for small dense graphs
- A negative diagonal entry signals a negative cycle
Intuition
The Floyd Warshall algorithm (also called the Floyd algorithm) finds the shortest path between all pairs of vertices with one idea, applied n times.
After round k, dist[i][j] holds the shortest path from i to j that may stop only at vertices 0 … k. Each round asks one question for every pair: is going i → k → j shorter than the best i → j so far?
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Once every vertex has been allowed as a stop, the matrix holds the true shortest distances. Each round builds on the one before it, which makes this dynamic programming.
The demo below steps through a Floyd Warshall algorithm example on four vertices, one relaxation at a time.
The all pairs shortest path problem: shortest distances between every pair of vertices, on a small or dense graph (n up to a few hundred), possibly with negative edges. When the whole distance matrix is the answer, three loops beat running a single-source algorithm from every vertex.
Approach
Before reading on: write the one-line update that tries vertex k as a stop between i and j. Then decide which of the three loops must be outermost, and why the other two orders give wrong answers.
Start from the edge matrix
dist already holds the direct edges, 0 on the diagonal and 10^8 for no edge. That is the answer when no intermediate vertex is allowed. Round 0 must see only direct edges; everything else is built from them.
Allow one more intermediate vertex per round
For k = 0 … n-1, try k as a stop on every path. After this round, paths may pass through any of 0 … k. Keep k as the outer loop: each round needs every distance from the previous round to be final.
Relax every pair through k
For every i and j: if both dist[i][k] and dist[k][j] are real (not 10^8) and their sum is smaller than dist[i][j], replace it. Going through k is either shorter or not; taking the minimum keeps the best of both. Skipping the 10^8 check can overflow and make an unreachable pair look reachable.
Read the matrix
After the last round, dist[i][j] is the shortest distance from i to j. A negative value on the diagonal, dist[i][i] < 0, means i lies on a negative cycle. After the last round every vertex has been allowed as a stop, so no shorter path can exist.
Floyd–Warshall Algorithm solution in Python | C++ | Java
k will allow one more vertex as a stop in the middle of a path.i → 0 → j. Its cost is dist[i][0] (row 0's column, green) plus dist[0][j] (row 0, green). Row and column 0 themselves cannot improve in this round, which is why updating in place is safe.dist[1][3]; later rounds can build on it.dist[2][1]; later rounds can build on it.dist[3][1]; later rounds can build on it.i → 1 → j. Its cost is dist[i][1] (row 1's column, green) plus dist[1][j] (row 1, green). Row and column 1 themselves cannot improve in this round, which is why updating in place is safe.dist[0][2]; later rounds can build on it.dist[3][2]; later rounds can build on it.i → 2 → j. Its cost is dist[i][2] (row 2's column, green) plus dist[2][j] (row 2, green). Row and column 2 themselves cannot improve in this round, which is why updating in place is safe.dist[0][3]; later rounds can build on it.dist[1][0]; later rounds can build on it.dist[1][3]; later rounds can build on it.i → 3 → j. Its cost is dist[i][3] (row 3's column, green) plus dist[3][j] (row 3, green). Row and column 3 themselves cannot improve in this round, which is why updating in place is safe.dist[1][0]; later rounds can build on it.dist[2][0]; later rounds can build on it.dist[2][1]; later rounds can build on it.k will allow one more vertex as a stop in the middle of a path.0..0.i → 1 → j. Its cost is dist[i][1] (row 1's column, green) plus dist[1][j] (row 1, green). Row and column 1 themselves cannot improve in this round, which is why updating in place is safe.dist[0][2]; later rounds can build on it.0..2.10^8 + (-3) is smaller than 10^8 and would be written into the matrix as a fake distance.k will allow one more vertex as a stop in the middle of a path.i → 0 → j. Its cost is dist[i][0] (row 0's column, green) plus dist[0][j] (row 0, green). Row and column 0 themselves cannot improve in this round, which is why updating in place is safe.dist[2][1]; later rounds can build on it.i → 1 → j. Its cost is dist[i][1] (row 1's column, green) plus dist[1][j] (row 1, green). Row and column 1 themselves cannot improve in this round, which is why updating in place is safe.dist[0][2]; later rounds can build on it.dist[i][i] < 0. The other entries keep falling with every lap, so they are not real shortest distances; the only safe output is to report the cycle.Common pitfalls
Putting k in an inner loop
for i in range(n):
for j in range(n):
for k in range(n):
...for k in range(n):
for i in range(n):
for j in range(n):
...With k innermost, dist[i][j] is finished before the entries it depends on have been improved, so paths that need two or more stops are missed. In the first example 1 → 0 needs the stops 2 and 3 (2 + 1 + 2 = 5), and the wrong order leaves it at 7.
Adding through a missing edge
if dist[i][k] + dist[k][j] < dist[i][j]:
if dist[i][k] == INF or dist[k][j] == INF:
continueIn the second example dist[1][0] becomes 10^8 - 3, a fake distance to a vertex that 1 cannot reach. With INT_MAX as infinity in C++ or Java, INT_MAX + INT_MAX overflows to a negative number and wins every comparison.
Complexity
n vertices. The matrix is updated in place, so no extra space beyond the input. With n = 100 that is one million relaxations, which is instant; at n = 5,000 it is too slow and one Dijkstra per source on a sparse graph is better.Floyd Warshall vs Dijkstra vs Bellman-Ford
All three find shortest paths. The number of sources and the sign of the weights decide which one fits.
| Algorithm | Sources | Negative edges? | Time |
|---|---|---|---|
| Floyd Warshall | all pairs | yes (detects negative cycles) | O(V³) |
| Dijkstra (binary heap) | one | no | O((V + E) log V) |
| Bellman-Ford | one | yes (detects negative cycles) | O(V · E) |
| Dijkstra from every vertex | all pairs | no | O(V (V + E) log V) |
Floyd–Warshall Algorithm FAQ
How does the Floyd Warshall algorithm work?
- State:
dist[i][j]= shortest distance fromitojusing only intermediate vertices0 … k. - Start: the edge matrix, with 0 on the diagonal and infinity for no edge.
- Round k: for every pair,
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). - End: after
k = n - 1, every vertex is allowed, sodistholds all-pairs shortest distances. - Complexity: O(n³) time, O(1) extra space.
- Negative cycles: some
dist[i][i] < 0after the loops.
What are the applications of the Floyd Warshall algorithm?
Distance tables between all cities in a small road network, routing tables, finding the vertex with the fewest reachable neighbours within a limit (LeetCode 1334), transitive closure of a relation (Warshall's algorithm, with or and and in place of min and +), and detecting negative cycles.
Can Floyd Warshall handle negative edge weights?
Yes. Unlike Dijkstra, it never assumes a distance is final early, so negative edges are fine. What it cannot handle is a negative cycle, because then no shortest path exists; it reports one as a negative diagonal entry.
What is the time complexity of the Floyd Warshall algorithm?
O(n³) time for n vertices, from the three nested loops, regardless of how many edges there are. Space is O(n²) for the matrix, or O(1) extra when it is updated in place.