Floyd-Warshall

The Intuition

Floyd-Warshall answers "for every pair of nodes, what is the shortest distance between them?" in one shot. The full output is a square table.

The starting table is what you already know from the edges. If there is a direct edge from i to j with weight w, dist[i][j] is w. If there is no direct edge, dist[i][j] is "very large". Distance from a node to itself is 0.

Now improve the table. Walk through every node k from 0 to V-1, and for every pair (i, j), check whether stopping at k makes the trip shorter. If dist[i][k] + dist[k][j] is less than the current dist[i][j], update. After all V values of k have been tried, every shortest path has been considered.

The reason this works is an inductive invariant on the outer loop: after the loop has processed nodes 0..k, the table dist[i][j] holds the shortest path from i to j that uses only nodes from {0, 1, ..., k} as intermediates. The relaxation step at iteration k+1 extends this by considering paths that route through k+1. Once k = V-1, every node has been allowed as an intermediate, so the table holds true all-pairs shortest paths.

The cost is V cubed because three nested loops each run V times. For 100 nodes that is a million operations, which finishes instantly. For 1000 nodes it is a billion, which is slow but still possible. For 10000 nodes you should pick a different approach (run Dijkstra from each source if all weights are non-negative, or Johnson's algorithm if they are not).

Negative weights are fine. A negative cycle is detected by checking the diagonal at the end. If any dist[i][i] is below zero, that node sits on a cycle whose total weight is negative, which means there is no real shortest path.

The pattern transfers beyond shortest distance. If you replace "+ and min" with "and / or", the same loop structure computes "is there a path from i to j" for every pair. That is called transitive closure. If you replace it with "× and max", the loop computes "what is the most reliable path" given edge probabilities.

When to use

All-pairs shortest paths on a small or medium graph (up to a few hundred or a thousand nodes). Transitive closure. Detecting negative cycles. Computing graph diameter. Anytime you need answers between every possible pair of nodes.

When NOT to use

The graph has thousands of nodes (V cubed is too slow)
You only need paths from one source (use Dijkstra or Bellman-Ford)
The graph is sparse and weights are non-negative (running Dijkstra V times is faster)

Pattern Recognition

shortest distance between every pair of citiesgraph diameteris there a path from any X to any Ysmallest number of stops between every pair

Edge Cases

the source and target are the same (distance is 0)
a node with no outgoing edges (its row stays at infinity except the diagonal)
multiple edges between the same pair (keep the smallest)
a sentinel value too close to overflow (cap at half of the int range and use early-exit on infinity)

Practice Problems

MediumFind the City With the Smallest Number of Neighbors at a Threshold Distance

MediumCourse Schedule IV

MediumNumber of Ways to Arrive at Destination

HardNumber of Restricted Paths From First to Last Node

MediumMinimum Cost to Convert String I

Key Points

•Use this when you need the shortest distance between every pair of nodes, not just one source.
•The whole graph is stored as a V by V table where dist[i][j] is the best known distance from i to j.
•The trick is to try every node k as a possible "stopover" between i and j.
•For each pair (i, j), check if going i to k to j is shorter than the current dist[i][j]. If yes, update.
•Three nested loops. The outer loop is the stopover k. The inner two loops are i and j.
•Works with negative edges. If any dist[i][i] becomes negative, a negative cycle exists.

Code Template

def floyd_warshall(n, edges):
    """
    Shortest distance between every pair of nodes.
    n: number of nodes (0..n-1).
    edges: list of (u, v, w) directed edges.
    Returns the full distance matrix.
    """
    INF = float('inf')
    # Start with infinity everywhere, except a node to itself is 0.
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        # If multiple edges exist, keep the smallest.
        if w < dist[u][v]:
            dist[u][v] = w

    # The key step. Try every node k as a stopover.
    # After the k-th outer iteration, dist[i][j] is the best path that uses
    # only nodes 0..k as stopovers.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

def has_negative_cycle(dist):
    """A negative cycle exists if any node has a negative distance to itself."""
    for i in range(len(dist)):
        if dist[i][i] < 0:
            return True
    return False

def reconstruct_path(n, edges, source, target):
    """Bonus: also returns the actual path, not just the distance."""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    nxt = [[None] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
            nxt[u][v] = v

    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]
                    nxt[i][j] = nxt[i][k]

    if nxt[source][target] is None:
        return None
    path = [source]
    while source != target:
        source = nxt[source][target]
        path.append(source)
    return path

func floydWarshall(n int, edges [][3]int) [][]int {
    // Shortest distance between every pair of nodes.
    const INF = int(1 << 30)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            if i == j {
                dist[i][j] = 0
            } else {
                dist[i][j] = INF
            }
        }
    }
    for _, e := range edges {
        u, v, w := e[0], e[1], e[2]
        if w < dist[u][v] {
            dist[u][v] = w
        }
    }

    // Try every node k as a stopover between i and j.
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            if dist[i][k] == INF {
                continue
            }
            for j := 0; j < n; j++ {
                if dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
    return dist
}

func hasNegativeCycle(dist [][]int) bool {
    for i := range dist {
        if dist[i][i] < 0 {
            return true
        }
    }
    return false
}

public class FloydWarshall {
    // edges: each row is {u, v, w}.
    public long[][] run(int n, int[][] edges) {
        long INF = Long.MAX_VALUE / 4;
        long[][] dist = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = (i == j) ? 0L : INF;
            }
        }
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (w < dist[u][v]) dist[u][v] = w;
        }

        // Try every node k as a stopover between i and j.
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        return dist;
    }

    public boolean hasNegativeCycle(long[][] dist) {
        for (int i = 0; i < dist.length; i++) {
            if (dist[i][i] < 0) return true;
        }
        return false;
    }
}

Common Mistakes

Putting i or j as the outermost loop instead of k (this gives wrong answers because intermediate stopovers must be added in order)
Initializing dist[i][i] to anything other than 0
Using a "very large" sentinel that overflows when added to an edge weight
Forgetting that this is O(V^3) and trying it on a graph with thousands of nodes

Related Patterns

The Intuition

Floyd-Warshall answers "for every pair of nodes, what is the shortest distance between them?" in one shot. The full output is a square table.

def floyd_warshall(n, edges): """ Shortest distance between every pair of nodes. n: number of nodes (0..n-1). edges: list of (u, v, w) directed edges. Returns the full distance matrix. """ INF = float('inf') # Start with infinity everywhere, except a node to itself is 0. dist = [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] = 0 for u, v, w in edges: # If multiple edges exist, keep the smallest. if w < dist[u][v]: dist[u][v] = w # The key step. Try every node k as a stopover. # After the k-th outer iteration, dist[i][j] is the best path that uses # only nodes 0..k as stopovers. for k in range(n): for i in range(n): if dist[i][k] == INF: continue for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist def has_negative_cycle(dist): """A negative cycle exists if any node has a negative distance to itself.""" for i in range(len(dist)): if dist[i][i] < 0: return True return False def reconstruct_path(n, edges, source, target): """Bonus: also returns the actual path, not just the distance.""" INF = float('inf') dist = [[INF] * n for _ in range(n)] nxt = [[None] * n for _ in range(n)] for i in range(n): dist[i][i] = 0 for u, v, w in edges: if w < dist[u][v]: dist[u][v] = w nxt[u][v] = v 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] nxt[i][j] = nxt[i][k] if nxt[source][target] is None: return None path = [source] while source != target: source = nxt[source][target] path.append(source) return path