Floyd-Warshall

Floyd-Warshall computes shortest paths between every pair of vertices.

It is useful when the graph is small enough and all-pairs distances are needed.

Core Idea

The algorithm gradually allows more intermediate vertices. When vertex k is allowed as an intermediate point, it checks whether going from i to j through k is shorter than the current known distance.

The time complexity is O(V^3), so it is not for very large graphs.

Function Contract

floyd_warshall(distance) expects a square matrix where distance[i][j] is the current direct distance from i to j, 0 on the diagonal, and float("inf") when no direct edge exists.

It mutates and returns the matrix so that each cell becomes the shortest known distance between that pair of vertices.

Python Example

def floyd_warshall(distance):
    n = len(distance)
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                distance[i][j] = min(
                    distance[i][j],
                    distance[i][k] + distance[k][j],
                )
 
    return distance

The input matrix should use 0 for the distance from a vertex to itself and inf where no edge exists.

State Meaning

The hidden DP idea is:

distance[i][j] after processing k means the shortest path from i to j using only allowed intermediate vertices up to k.

When vertex k becomes allowed, the algorithm checks whether i -> k -> j improves the known path from i to j.

Step-by-Step Update

For each triple (i, k, j), the algorithm compares:

current path: i -> j
new path:     i -> k -> j

If the new path is cheaper, it replaces the old distance.

Complexity

The three nested loops give O(V^3) time. The matrix uses O(V^2) space.

This can be excellent for small graphs with many all-pairs queries, but too expensive for large sparse graphs.

Failure Example

A negative cycle appears when some distance[i][i] becomes negative after the algorithm. That means a path can leave i, return to i, and reduce total cost.

All-pairs distances affected by such a cycle need special interpretation because shortest paths may be undefined.

Common Confusions

Floyd-Warshall is not a single-source shortest path algorithm. It computes distances for every source-target pair.

The algorithm can handle negative edges, but negative cycles require separate detection and interpretation.

Another common mistake is using Floyd-Warshall when only one start vertex matters. Dijkstra or Bellman-Ford may be more appropriate for single-source queries.

When To Use It

Use Floyd-Warshall when the graph is small, many all-pairs shortest path queries are needed, or the matrix form is natural.

Do not use it for large graphs unless the constraints clearly allow O(V^3).

The Main Point

Floyd-Warshall is all-pairs dynamic programming over intermediate vertices. It is simple and powerful when O(V^3) is acceptable.