A payments team keeps 24 clearing nodes. Every morning a job fills a 24-by-24 table: cheapest fee from each node to every other. The first version spun 24 Dijkstras off a neighbor list. Fine at 24. Someone reused the job on the full merchant graph — 6,000 vertices, sparse. The batch did not finish before the next cutover. Nobody “chose a slow algorithm.” They ran an all-pairs procedure whose cost is cubic in n on a graph that was no longer small.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for every triple; after all k, every pair has considered every intermediate. The layout is a dense matrix, not a neighbor list (Graphs). Families and the catalog live on the Algorithms Roadmap. It is not n Dijkstras on a huge sparse graph, not Bellman-Ford, and not a reason to cube a mesh with thousands of vertices.

The table is n by n, the loop is k

Dijkstra is single-source when every weight is non-negative. Bellman-Ford is single-source when a negative edge is allowed. Floyd-Warshall is every source to every destination in one n³ pass. Wave 4 cousins, one sentence each, stop.

You need a cell for every pair, including “no edge.” That is an adjacency matrix: 0 on the diagonal, edge weights where an edge exists, infinity elsewhere. The graph post already owns list vs matrix; this post consumes the dense table.

Negative edges are allowed. A negative cycle is not a number you can report — you could loop forever and the cost keeps dropping. After the loops, a negative on the diagonal is that cycle. Sparse all-pairs with negatives has a name (Johnson). This post will not implement it.

n Dijkstras on a 6,000-vertex merchant graph is not an all-pairs strategy. Neither is Floyd-Warshall on that graph.

Relax through every intermediate k

Index vertices 0 … n-1. dist[i][j] starts as the direct edge i → j, or infinity, or 0 when i == j. Then, for each possible intermediate k, try routing i ⇝ j through k:

  1. Outer k. “Paths that may use k (and any already-processed intermediates).” k must be outermost. Nest it inside and the DP layer is wrong.
  2. Then i, then j. If dist[i][k] or dist[k][j] is infinity, skip — there is no path to add.
  3. Write dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

After k has run through every vertex, dist[i][j] is the shortest i ⇝ j using any intermediates, or still infinity. You do not grow a frontier. You fill a table.

Note: Directed or undirected is the layout’s job. Undirected means both dist[u][v] and dist[v][u] already hold the same weight unless the domain is asymmetric.

Keep an optional next[i][j] beside dist if you must emit a path: when you write a better dist[i][j] via k, set next[i][j] = next[i][k], then walk next from i toward j. The sketch below does not build next.

A walked 4-vertex matrix

Four vertices. The expensive directs A → C and A → D are the trap: the cheap route to D is three hops through B and C.

directed, 4 vertices:

  A --3--> B --2--> C --1--> D
  A --10-> C
  A --15-> D
  B --8--> D

init dist (∞ = no edge):
      A   B   C   D
  A   0   3  10  15
  B   ∞   0   2   8
  C   ∞   ∞   0   1
  D   ∞   ∞   ∞   0

k = A  (nobody except A reaches A)
  no updates

k = B
  A→C via B: 3+2 = 5  < 10  → dist[A][C]=5
  A→D via B: 3+8 = 11 < 15  → dist[A][D]=11
      A   B   C   D
  A   0   3   5  11
  B   ∞   0   2   8
  C   ∞   ∞   0   1
  D   ∞   ∞   ∞   0

k = C
  A→D via C: 5+1 = 6 < 11  → dist[A][D]=6
  B→D via C: 2+1 = 3 <  8  → dist[B][D]=3
      A   B   C   D
  A   0   3   5   6
  B   ∞   0   2   3
  C   ∞   ∞   0   1
  D   ∞   ∞   ∞   0

k = D  (D has no outgoing except the 0 diagonal)
  no updates

all-pairs:
  A→D cost 6   via A → B → C → D
  not:         A → D            cost 15
  not:         A → B → D        cost 11
  D reaches only D; A, B, C never reach A (∞ stays)

diagonal 0,0,0,0  → no negative cycle

Each k is one complete layer. A → D dropped from 15 to 11 through B, then to 6 through C once A → C was already 5. Empty graph: identity matrix of zeros, infinity off-diagonal, triple loop writes nothing.

Negative on the diagonal

After every k, dist[i][i] should still be 0. A negative edge B → A of -2 against A → B of 1 makes a cycle of -1. The same recurrence writes dist[A][A] = -1 (and dist[B][B] = -1). That is the detector: scan the diagonal; any dist[i][i] < 0 means a negative cycle is reachable from i to itself.

You cannot return “shortest paths” from that table. Looping the cycle makes any path that touches it arbitrarily cheap. Report the cycle; do not treat the numbers as distances.

Note: Negative edges without a negative cycle are fine. First-pop-is-final is Dijkstra’s rule, not this one. Do not skip Floyd-Warshall because a weight is negative.

Java sketch

Dense int[][] dist. Vertices are 0 … n-1. Infinity is a sentinel; skip it before you add, and add in long so two large sentinels do not wrap.

static final int INF = Integer.MAX_VALUE;

static int[][] floydWarshall(int n, int[][] edges) {
    int[][] dist = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], INF);
        dist[i][i] = 0;
    }
    for (int[] e : edges) { // {from, to, weight}
        int u = e[0], v = e[1], w = e[2];
        dist[u][v] = Math.min(dist[u][v], w);
    }

    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[k][j] == INF) continue;
                long nd = (long) dist[i][k] + dist[k][j];
                if (nd < dist[i][j]) {
                    dist[i][j] = (int) nd;
                }
            }
        }
    }
    return dist;
}

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

String IDs need a side map to 0 … n-1, same as the graph post’s matrix. Parallel edges keep the min on init. long[][] if a real path cost can exceed Integer.MAX_VALUE even without the sentinel.

Note: INF + INF as int wraps to a negative. The continue on INF and the long add are the guard. Unreachable pairs left at INF are a sentinel, not a cost you may add to.

Complexity

Let n be vertices. Three nested loops, every triple, every time. No heap, no early exit that changes the bound.

TimeO(n³) — always; `
Extra RAMO(n²) dist; optional next[][] the same size
After all kShortest i ⇝ j, or still infinity
Negative cycleSome dist[i][i] < 0
JohnsonName only: sparse all-pairs with negatives; do not implement

Glossary and the Big-O reading live on the hub. The bill that kills the merchant job is n in the thousands, not a missing heap.

n ≈ 400 is tens of millions of triples — a batch is fine. n ≈ 4,000 is tens of billions. That is not a request-path algorithm.

When not to run Floyd-Warshall

Skip it when:

  • You have one source and every weight is ≥ 0. Dijkstra already returns those distances. Cubing the whole table is cargo-cult of all-pairs.
  • You have one source and a negative edge. Bellman-Ford is the cousin; this post does not walk it.
  • n is huge and the graph is sparse. n Dijkstras (non-negative) can beat n³. Floyd-Warshall does not get cheaper when most cells are infinity.
  • You needed “is u connected to v?” That is hasEdge / a reachability walk, not a distance matrix.
  • A library already routes. Map SDKs, service-mesh control planes, and graph DBs already fill pair costs. Pasting this sketch into a request path is the wrong system boundary.

Do not run Floyd-Warshall on a sparse 10k-vertex graph when you needed one source, or when n³ will not finish. Do not spin n Dijkstras on a 24-node dense table you could have cubically filled.

Also skip it when you only needed hop count from one s: that is BFS. This post is all-pairs on a weighted matrix.

JDK: an int[][], not a FloydWarshall class

There is no java.util.FloydWarshall. The library pieces are the table:

  • Layout: int[][] (or long[][]) as in the graph post’s matrix
  • Init: Arrays.fill to infinity, then dist[i][i] = 0
  • Optional path: a next[][] you fill on improve, then walk

Prefer the cubic matrix when n is tens to low hundreds and you need every pair. Reach for Dijkstra when there is one source and weights stay non-negative.

Do not nest k inside i and j. Do not add infinity. Do not implement Johnson because a complexity table named one.

Cheat sheet

Job:        all-pairs shortest path; n small enough for n³
Layout:     dense dist[n][n] — 0 diagonal, weights, ∞ elsewhere
Recurrence: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Loop:       k outer, then i, then j; skip if dist[i][k] or dist[k][j] is ∞
Negative:   edges ok; cycle iff some dist[i][i] < 0 after the loops
Path:       optional next[i][j] on improve — not required to fill dist
Single-src: Dijkstra (≥ 0) or Bellman-Ford (negatives) — not this
Sparse/big: n Dijkstras, or Johnson (name only)
JDK:        int[][]; no FloydWarshall type
Do not:     cube a huge sparse graph; n Dijkstras on a tiny dense table

Do:

  • Put k outermost. That is the DP.
  • Skip infinity before you add. Add in long.
  • Scan the diagonal when a negative cycle would poison the table.

Don’t:

  • Run n³ on a 6,000-vertex sparse merchant graph because the 24-node job used the same name.
  • Nest k inside the pair loops.
  • Treat a negative diagonal as a distance.
  • Implement Johnson, or paste the sketch into a request path a library already routes.

Wrap-up

Floyd-Warshall is DP on a dense n × n table: try every intermediate k, relax every pair, skip infinity. After all k, every pair has considered every intermediate. Negative edges are legal; a negative on the diagonal is a cycle, not a cost. The JDK gives you int[][], not a turnkey all-pairs router. Use it when n is small and you need every pair. Hand the single-source case to Dijkstra or Bellman-Ford. Do not cube a graph whose size is the merchant batch.

The next procedure in this wave is Dijkstra plus a heuristic: estimate remaining cost, then order the heap by f = g + h.

Next optional step in the series Dijkstra plus a heuristic when you can estimate remaining cost. A-Star: Dijkstra Plus a Heuristic When You Can Estimate Remaining Cost