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

Floyd-Warshall computes shortest costs between every pair of vertices. Instead of selecting source frontiers, it gradually permits more intermediate vertices on paths. A matrix is natural when every pair's result is needed and the graph is small enough for cubic work.

A prototype can run Bellman-Ford once per source and collect distance rows. The final recurrence shares work among all pairs.

Allowing one more intermediate stop

Let phase k permit intermediate vertices from the first k choices. A route from i to j either avoids the new vertex or decomposes into i-to-k and k-to-j. Put k outside the i/j loops so every update follows that phase invariant; casually permuting loop order can lose it.

Initialize each diagonal to zero, retain the cheapest parallel edge, and combine only two reachable costs. A negative self-loop must override zero. After relaxation, any negative diagonal identifies a negative cycle anywhere in the graph; this global error scope differs from single-source Bellman-Ford.

Allocate independent matrix rows in JavaScript. Array(n).fill(Array(n).fill(null)) aliases every row, so changing one distance would modify unrelated rows. Missing paths stay null and must not be coerced into zero arithmetic. Empty n=0 has an empty matrix and no cycle.

const n = 3;
const distance = Array.from({length: n}, () => Array(n).fill(null));
distance[0][0] = 0;
console.log(distance[1][0]); // null: row storage is independent
const via = [3, 2];
console.log(via[0] + via[1]); // 5: a route through one known intermediate

Knowing when the full matrix is worthwhile

Floyd-Warshall costs O(V³) time and O(V²) storage. Repeated Bellman-Ford costs O(V²(E+1)), which can be worse for dense input. Use all-pairs preprocessing when many source/target queries justify it. For one source or a sparse large graph, a single-source algorithm avoids unnecessary matrix work.

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