Floyd–Warshall all-pairs shortest paths

A small warehouse map answers route-cost questions between many pairs of loading bays throughout a shift. Running a fresh shortest-path search for every pair repeats work; the map is small enough to prepare a complete distance table.

Floyd–Warshall builds that table by allowing intermediate vertices one at a time. The outer loop has a meaning: it decides which stops the routes may use, rather than merely controlling the order of arithmetic.

Preparing routes between every loading bay

Compute cheapest routes for every ordered vertex pair, including parallel edges and negative costs. Any negative cycle anywhere invalidates the full matrix contract.

Running a single-source method from every vertex is a useful baseline. Floyd–Warshall instead extends the set of allowed intermediate vertices in a fixed outer-loop order; arbitrary loop interchange loses that meaning.

Allowing one more intermediate stop

With direct costs 0 → 1: 3, 1 → 2: 2, and 0 → 2: 9, allowing stop 1 improves the last route to five. For each pair, compare its existing cost with the cost via the newly allowed stop. Keep the intermediate-stop loop outside both endpoint loops; changing that order loses the staged dependency the update relies on.

The intermediate-vertex loop must be outermost: after k, each cell is optimal using only allowed intermediates through k. Guard unreachable operands before addition. Keep the cheapest parallel edge and zero diagonal; a negative diagonal after relaxation detects a negative cycle anywhere. Final O(V³) time, O(V²) space.

One cell update compares its existing route with a route through a specific allowed intermediate:

import java.util.*;

class Example {
    public static void main(String[] args) {
        Long direct = 9L;
        Long toIntermediate = 3L;
        Long fromIntermediate = 2L;
        long through = toIntermediate + fromIntermediate;
        assert through < direct;
        assert through == 5;
    }
}

This arithmetic is valid only when both route halves are reachable. The full recurrence must preserve the intermediate-vertex invariant, keep the cheapest parallel edge, and inspect negative diagonal entries after relaxation.

Knowing when the full matrix is worthwhile

All-pairs distances suit dense small graphs and repeated pair queries. O(V²) retained output and O(V³) processing become expensive quickly, so sparse or one-source workloads may need another approach.

Return an n-by-n Long distance matrix with null for unreachable pairs. Directed edges may be negative. n=0 returns empty. Reject negative n, invalid endpoints, or any negative cycle. Prototype may run Bellman–Ford from each source.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

The warehouse gets cheap later lookups by accepting the cost of preparing and storing every pair.