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.

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.

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.

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.