Floyd–Warshall: shortest paths between all pairs

A table for every pair

BFS, Dijkstra and Bellman–Ford start from one source. Floyd–Warshall computes all ordered source–destination pairs. Row i is the starting vertex and column j is the destination: d[i][j] is a cost, not an edge count. Directed edges need not have a reverse edge.

Initially use zero on the diagonal, the smallest direct edge weight for connected pairs and infinity otherwise. Zero on the diagonal represents staying put; a negative self-loop replaces it. Infinity means no route is known yet. A negative edge alone does not imply a negative cycle.

Try a route through k

For each new intermediate vertex k, compare d[i][j] with d[i][k] + d[k][j]. If both parts exist and their sum is strictly smaller, improve the entry. The two parts may already contain earlier intermediate vertices. Equal costs keep the previous route; the algorithm does not minimize the number of edges among equal-cost paths.

In a graph without negative cycles, after stage k every entry is optimal among paths whose internal vertices belong to the processed prefix. Before any stage, no internal vertices are allowed. The outer k loop is essential; exchanging it with the pair loops generally breaks this invariant.

This demo reads a fixed previous-stage matrix and displays all pair updates together. The amber row and column supply the two terms. Green cells improved in this stage; the outlined cell is your selected pair. A step that merely announces the next k has not applied its updates yet. Counters count V² pair checks per applied stage, including missing routes; updates count strict improvements.

A → D: 10, then 9, then 3

The direct edge A → D costs 10. When B becomes available internally, A → B → D costs 3 + 6 = 9. In the same stage A → C becomes 3 + (−2) = 1. Both entries change together.

At stage C, the already known A → C route combines with C → D: 1 + 2 = 3. The route is A → B → C → D. The final rows are A: [0, 3, 1, 3], B: [∞, 0, −2, 0], C: [∞, ∞, 0, 2], D: [∞, ∞, ∞, 0]. Select D → A: it is unreachable, although A → D exists. All-unit weights would make minimum cost equal minimum edge count.

Reconstructing a route

The next-hop matrix stores the first vertex after i on the current i → j route. A direct edge sets next[i][j]=j. Improving through k copies the first hop from the old i → k route. Following these hops reconstructs a finite route; staying at the same vertex has a one-vertex route of cost zero unless a negative cycle affects that pair.

The player computes the whole matrix regardless of your selected endpoints. Changing the selected pair or clicking a cell pauses playback and changes the graph highlight without recomputing the algorithm. Links preserve the exact graph, selected pair, step and speed on a clean player page. Video export captures the whole run from the beginning, without narration or music.

Which pairs have no finite minimum?

After all V stages, a negative diagonal entry d[k][k] reveals a negative closed walk. Mark pair i → j as −∞ precisely when some such k is reachable from i and j is reachable from k. Repeating the cycle makes the total cost arbitrarily small. No finite shortest route is returned for these pairs. A disconnected negative cycle does not invalidate finite answers elsewhere.

The cycle preset adds C → B with weight 1: B → C → B totals −1. A → D becomes unbounded, while D → A stays unreachable and D → D stays zero. The disconnected preset adds an isolated negative self-loop at E; A → D still costs 3. While a negative cycle is being processed, finite table entries are provisional walk costs, not shortest-path answers; a looping next-hop chain is not drawn.

Time, memory and scope

The algorithm takes Θ(V³) time and Θ(V²) working memory, including next hops and two matrix layers. A classic in-place implementation also needs Θ(V²) space; this version keeps separate layers so a visual stage is independent of pair scan order. Negative-cycle pair classification takes O(V³) additional time and O(V²) reachability space, preserving the overall bounds.

The player stores O(V) immutable frames of O(V²) entries each: its history uses O(V³) memory, separate from the algorithm's working memory. The interactive input is limited to six vertices and unique directed pairs with integer weights from −99 to 99. The article function accepts parallel edges and keeps the lightest, validates integer weights and rejects unsafe sums. Fractional weights need a separate numerical error policy.

Floyd–Warshall is convenient when many pair queries need answers and a quadratic matrix is affordable. For one source or a large sparse graph, compare source-based algorithms instead. For unit costs use BFS; for nonnegative weights use Dijkstra; Bellman–Ford handles negative edges from one source.

JavaScript implementation

The function follows the demo's fixed-layer recurrence and returns distances, next hops, negative diagonal witnesses and a route query. Infinity means unreachable, −Infinity means no finite minimum. The checks prevent silently overflowing JavaScript's safe integer range.

function floydWarshall(n, edges) {
    if (!Number.isInteger(n) || n < 1) throw Error("Invalid vertex count");
    const valid = v => Number.isInteger(v) && v >= 0 && v < n;
    let d = Array.from({length: n}, (_, i) =>
        Array.from({length: n}, (_, j) => i === j ? 0 : Infinity));
    let next = Array.from({length: n}, (_, i) =>
        Array.from({length: n}, (_, j) => i === j ? i : null));
    for (const {from, to, weight} of edges) {
        if (!valid(from) || !valid(to) || !Number.isSafeInteger(weight))
            throw Error("Invalid edge");
        if (weight < d[from][to]) {
            d[from][to] = weight; next[from][to] = to;
        }
    }
    for (let k = 0; k < n; k++) {
        const before = d, oldNext = next;
        d = before.map(row => [...row]);
        next = oldNext.map(row => [...row]);
        for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {
            if (!Number.isFinite(before[i][k]) || !Number.isFinite(before[k][j]))
                continue;
            const candidate = before[i][k] + before[k][j];
            if (!Number.isSafeInteger(candidate)) throw Error("Cost overflow");
            if (candidate < before[i][j]) {
                d[i][j] = candidate; next[i][j] = oldNext[i][k];
            }
        }
    }
    const negative = d.flatMap((row, k) => row[k] < 0 ? [k] : []);
    const reachable = d.map(row => row.map(Number.isFinite));
    for (let i = 0; i < n; i++) for (let j = 0; j < n; j++)
        if (negative.some(k => reachable[i][k] && reachable[k][j])) {
            d[i][j] = -Infinity; next[i][j] = null;
        }
    function path(from, to) {
        if (!valid(from) || !valid(to)) throw Error("Invalid pair");
        if (!Number.isFinite(d[from][to])) return [];
        const route = [from];
        while (from !== to) {
            const hop = next[from][to];
            if (hop === null || route.includes(hop) || route.length >= n)
                throw Error("Invalid next-hop chain");
            route.push(hop); from = hop;
        }
        return route;
    }
    return {distance: d, next, negative, path};
}

// A=0, B=1, C=2, D=3
const result = floydWarshall(4, [
    {from: 0, to: 1, weight: 3}, {from: 1, to: 2, weight: -2},
    {from: 2, to: 3, weight: 2}, {from: 0, to: 3, weight: 10},
    {from: 1, to: 3, weight: 6}
]);
console.log(result.distance[0][3]); // 3
console.log(result.path(0, 3));     // [0, 1, 2, 3]