All pairs: the Floyd–Warshall algorithm

Lesson · 10 min read · Graphs · Shortest paths between all pairs

Shortest distances between every pair of nodes in three nested loops, by allowing one more intermediate node at a time.

The problem

Single-source algorithms answer "how far is everything from here?". Some questions need the distance between every pair: a table of travel times between all offices, the most central node of a network, every city's reachable neighbours within a budget. Dijkstra run from each node does it in O(n · m log n). When the graph is small or dense, or weights can be negative, Floyd–Warshall is simpler and often faster.

Four nodes, six weighted directed edges. The cheapest way from 0 to 2 is 0 → 1 → 2 (cost 4), not the direct edge (cost 7).

The idea: one more intermediate at a time

Number the nodes 0 to n − 1. Let d_k[i][j] be the length of the shortest path from i to j whose intermediate nodes all lie in {0, …, k}. With no intermediates allowed, that is just the edge weight (or ∞). Allowing node k as well gives exactly two options: the best path either avoids k, or goes through it once, from i to k and then from k to j, each part using only intermediates below k:

d[i][j] = min( d[i][j], d[i][k] + d[k][j] )

Applying that update for k = 0, 1, …, n − 1 in turn ends with every intermediate allowed: the true shortest distances. The table can be updated in place, because row k and column k do not change during round k (d[k][k] is 0).

Floyd–Warshall

floydWarshall(n, edges)

Fill d with ∞, put 0 on the diagonal, and d[u][v] = min(d[u][v], w) for each edge.
For k from 0 to n − 1, for every i, for every j: if d[i][k] + d[k][j] < d[i][j], replace d[i][j].
If some d[i][i] < 0 at the end, the graph has a negative cycle.

The order of the loops matters: k must be the outermost. With k inside, a path would be extended through an intermediate before the paths it relies on had been computed.

Step by step

The matrix for the graph above after each round. Shaded cells are the row and column of the new intermediate; amber cells changed.

Floyd–Warshall on four nodes: one frame per intermediate node k.

Step 1 / 5

Start: 0 on the diagonal, the edge weight where there is an edge, ∞ everywhere else. These are the shortest paths that use no intermediate node.
Step 2 / 5

k = 0: allow paths through node 0. Row 0 and column 0 (shaded) are read; 2 entries improve: 3→1 = 4, 3→2 = 8.
Step 3 / 5

k = 1: allow paths through node 1. Row 1 and column 1 (shaded) are read; 2 entries improve: 0→2 = 4, 3→2 = 5.
Step 4 / 5

k = 2: allow paths through node 2. Row 2 and column 2 (shaded) are read; 2 entries improve: 0→3 = 6, 1→3 = 3.
Step 5 / 5

k = 3: allow paths through node 3. Row 3 and column 3 (shaded) are read; 3 entries improve: 1→0 = 4, 2→0 = 3, 2→1 = 6. Every node has been allowed as an intermediate: the matrix holds all shortest distances.

Implementation

Distances between every pair, with −1 for pairs that cannot be reached:

def all_pairs(n, edges):
    INF = float('inf')
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)          # keep the lighter of parallel edges
    for k in range(n):                     # allow k as an intermediate node
        dk = d[k]
        for i in range(n):
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(n):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
    return [[-1 if x == INF else x for x in row] for row in d]

#include <algorithm>
#include <climits>
#include <vector>

std::vector<std::vector<long long>> solve(int n, const std::vector<std::vector<int>>& edges) {
    const long long INF = LLONG_MAX / 4;
    std::vector<std::vector<long long>> d(n, std::vector<long long>(n, INF));
    for (int i = 0; i < n; ++i) d[i][i] = 0;
    for (const auto& e : edges) d[e[0]][e[1]] = std::min<long long>(d[e[0]][e[1]], e[2]);
    for (int k = 0; k < n; ++k)                       // allow k as an intermediate
        for (int i = 0; i < n; ++i) {
            if (d[i][k] == INF) continue;
            for (int j = 0; j < n; ++j)
                if (d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        }
    for (auto& row : d)
        for (auto& x : row)
            if (x == INF) x = -1;
    return d;
}

class Solution {
    public int[][] allPairs(int n, int[][] edges) {
        final long INF = Long.MAX_VALUE / 4;
        long[][] d = new long[n][n];
        for (int i = 0; i < n; i++) {
            java.util.Arrays.fill(d[i], INF);
            d[i][i] = 0;
        }
        for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
        for (int k = 0; k < n; k++)                    // allow k as an intermediate
            for (int i = 0; i < n; i++) {
                if (d[i][k] == INF) continue;
                for (int j = 0; j < n; j++)
                    if (d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
            }
        int[][] out = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) out[i][j] = d[i][j] == INF ? -1 : (int) d[i][j];
        return out;
    }
}

function allPairs(n, edges) {
  const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
  for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);   // lighter parallel edge
  for (let k = 0; k < n; k++) {                                   // allow k as an intermediate
    for (let i = 0; i < n; i++) {
      if (d[i][k] === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
      }
    }
  }
  return d.map(row => row.map(x => (x === Infinity ? -1 : x)));
}

fn solve(n: i64, edges: &[[i64; 3]]) -> Vec<Vec<i64>> {
    let n = n as usize;
    let mut d: Vec<Vec<Option<i64>>> = (0..n).map(|i| (0..n).map(|j| if i == j { Some(0) } else { None }).collect()).collect();
    for e in edges {
        let (u, v, w) = (e[0] as usize, e[1] as usize, e[2]);
        d[u][v] = Some(d[u][v].map_or(w, |x| x.min(w)));   // lighter parallel edge
    }
    for k in 0..n {                                       // allow k as an intermediate
        for i in 0..n {
            let Some(dik) = d[i][k] else { continue };
            for j in 0..n {
                if let Some(dkj) = d[k][j] {
                    if d[i][j].map_or(true, |x| dik + dkj < x) {
                        d[i][j] = Some(dik + dkj);
                    }
                }
            }
        }
    }
    d.into_iter().map(|row| row.into_iter().map(|x| x.unwrap_or(-1)).collect()).collect()
}

import Data.List (foldl')
import qualified Data.Map.Strict as M

solve :: Int -> [[Int]] -> [[Int]]
solve n edges = [[maybe (-1) id (M.lookup (i, j) final) | j <- [0 .. n - 1]] | i <- [0 .. n - 1]]
  where
    -- a map holds only the finite distances; a missing key is infinity
    start = M.fromListWith min ([((i, i), 0) | i <- [0 .. n - 1]] ++ [((u, v), w) | [u, v, w] <- edges])
    final = foldl' through start [0 .. n - 1]
    through d k = M.fromList
      [ ((i, j), best)
      | i <- [0 .. n - 1], j <- [0 .. n - 1]
      , let viaK = (+) <$> M.lookup (i, k) d <*> M.lookup (k, j) d
      , Just best <- [minMaybe (M.lookup (i, j) d) viaK] ]
    minMaybe (Just a) (Just b) = Just (min a b)
    minMaybe a Nothing = a
    minMaybe Nothing b = b

The same code is the reference solution to Distances between every pair of nodes, where it is compiled and run against the tests in all six languages.

TimeO(n³)

SpaceO(n²)

n = 400 means 64 million updates: fine. n = 10⁴ is a trillion: use Dijkstra from each source instead, or ask whether all pairs are really needed.

To recover the paths and not just their lengths, keep a table next[i][j]: the first step on the best path from i to j. Set it to j for each edge and, whenever a path through k wins, copy next[i][k].