All-Pairs Shortest Paths Overview

Formally, let `G = (V, E)` be a directed graph with `n = |V|` vertices and `m = |E|` edges, and let `w: E → ℝ` assign a real-valued weight to each edge. The all-pairs shortest paths problem asks for a function `δ: V × V → ℝ ∪ {∞}` such that `δ(u, v)` equals the weight of a minimum-weight path from `u` to `v`, or `∞` if no such path exists. If the graph contains a cycle of negative total weight reachable from `u` and able to reach `v`, then `δ(u, v)` is conventionally defined as `-∞`, since paths can be made arbitrarily cheap by looping the negative cycle — most APSP algorithms are only defined to work correctly when no such cycle exists, and are expected to detect one if it does. The standard output representation is the distance matrix `D`, an `n × n` array where `D[i][j] = δ(i, j)`, with `D[i][i] = 0` for all `i` (the empty path) and `D[i][j] = ∞` when `j` is unreachable from `i`. A companion predecessor matrix `Π`, where `Π[i][j]` stores the vertex immediately preceding `j` on a shortest `i→j` path, lets any shortest path be reconstructed in time proportional to its length by walking backward from `j` to `i`. Together `(D, Π)` are the canonical APSP output; almost every APSP algorithm, however it computes them internally, ultimately produces exactly these two matrices. Because the answer is inherently `Θ(n²)` in size, any correct APSP algorithm needs at least `Ω(n²)` time just to write the output down (assuming a dense-ish answer; on graphs where most pairs are unreachable this bound can be looser, but the worst case dominates asymptotic analysis). This lower bound is the yardstick: an APSP algorithm is considered good if it approaches `Θ(n²)` work per unit of useful information, and the repeated-SSSP baseline is judged by how close its per-source cost, multiplied by `n`, comes to that bound.

The repeated-SSSP baseline is conceptually simple: for every vertex `s`, treat `s` as a single source, run an SSSP algorithm, and copy the resulting distance array into row `s` of `D` (and the predecessor array into row `s` of `Π`). The only design decision is which SSSP algorithm to run, and that choice depends entirely on whether the graph has negative edge weights.

Case 1 — nonnegative weights. Dijkstra's algorithm is correct and asymptotically optimal for a single source with nonnegative weights, so running it from every vertex is the natural choice.

Case 2 — negative weights allowed, no negative cycles. Dijkstra's greedy invariant breaks under negative edges (a vertex popped from the priority queue can later be improved by a negative-weight edge), so Bellman-Ford, which tolerates negative weights and explicitly detects negative cycles, must be used instead.

Case 3 — negative weights, but you still want Dijkstra's speed. Johnson's algorithm reweights every edge using a single Bellman-Ford run from an auxiliary source, producing an equivalent nonnegative-weight graph on which Dijkstra can safely be run `n` times. This is the bridge between the two baselines and the dense-graph dynamic programming methods that follow it. ``` // Baseline 1: Repeated Dijkstra (requires nonnegative weights) function APSP-DIJKSTRA(G, w): n = |V(G)| initialize D as n×n matrix, Π as n×n matrix for each vertex s in V(G): dist, pred = DIJKSTRA(G, w, s) // standard single-source Dijkstra for each vertex v in V(G): D[s][v] = dist[v] Π[s][v] = pred[v] return D, Π // Baseline 2: Repeated Bellman-Ford (handles negative weights, detects negative cycles) function APSP-BELLMAN-FORD(G, w): n = |V(G)| initialize D as n×n matrix, Π as n×n matrix for each vertex s in V(G): dist, pred, ok = BELLMAN-FORD(G, w, s) if not ok: report "negative-weight cycle reachable from s" return FAILURE for each vertex v in V(G): D[s][v] = dist[v] Π[s][v] = pred[v] return D, Π // Bridge: Johnson's reweighting, enabling Dijkstra despite negative edges function JOHNSON(G, w): add new vertex q with a zero-weight edge q -> v for every v in V(G) h, _, ok = BELLMAN-FORD(G ∪ {q}, w, q) if not ok: report "negative-weight cycle in G" return FAILURE for each edge (u, v) in E(G): w'(u, v) = w(u, v) + h[u] - h[v] // reweighted, provably nonnegative remove q initialize D as n×n matrix for each vertex s in V(G): dist', pred = DIJKSTRA(G, w', s) for each vertex v in V(G): D[s][v] = dist'[v] - h[s] + h[v] // undo the reweighting return D ``` The reweighting step deserves a moment of care, because it is the least obvious line in the whole pipeline. Define `h(v) = δ_{q}(v)`, the shortest distance from the auxiliary source `q` to `v` in the augmented graph. Since `q` has a zero-weight edge to every vertex, `h(v)` is finite for all `v`, and by the triangle inequality for shortest-path distances, `h(v) ≤ h(u) + w(u, v)` for every edge `(u, v)`. Rearranging gives `w(u, v) + h(u) - h(v) ≥ 0`, which is exactly the claim that `w'` is nonnegative. Moreover, for any path `P` from `s` to `t`, the reweighted length telescopes: ``` w'(P) = w(P) + h(s) - h(t) ``` because every intermediate `+h(v)` from leaving `v` cancels the `-h(v)` from entering `v`. Since the additive correction `h(s) - h(t)` is the same for every `s→t` path, the path that minimizes `w(P)` is exactly the path that minimizes `w'(P)`, so shortest paths are preserved and only need the constant correction `-h(s) + h(t)` undone at the end, which the final line of `JOHNSON` performs.

Repeated Dijkstra. A single run of Dijkstra's algorithm with a binary heap costs `O((V + E) log V) = O(E log V)` for a connected graph. Running it once per vertex gives: ``` O(V · E log V) ``` For a sparse graph, `E = O(V)`, so this is `O(V² log V)` — very close to the `Θ(V²)` output-size lower bound, with only a logarithmic overhead. Using a Fibonacci heap improves a single run to `O(E + V log V)`, giving an overall bound of `O(VE + V² log V)`, which is the best known repeated-SSSP bound for nonnegative weights. For dense graphs (`E = Θ(V²)`), the binary-heap version costs `O(V³ log V)`, which is worse than the `Θ(V³)` dynamic-programming methods this baseline foreshadows.

Repeated Bellman-Ford. A single Bellman-Ford run costs `O(V·E)` because it relaxes all edges over `V - 1` rounds. Repeating it from every source gives: ``` O(V² · E) ``` This is markedly worse than repeated Dijkstra, and for dense graphs it becomes `O(V⁴)`. It is the correct choice only when negative edges are present and reweighting is undesirable or a full APSP negative-cycle audit is wanted directly from every source.

Johnson's algorithm. One Bellman-Ford run on the augmented graph costs `O(VE)`. Reweighting all edges costs `O(E)`. Then `n` Dijkstra runs on the reweighted (now nonnegative) graph cost `O(V·E log V)` with a binary heap, or `O(VE + V² log V)` with a Fibonacci heap. The total is dominated by the Dijkstra phase: ``` O(VE + V² log V) [Fibonacci-heap Johnson's] ``` which is strictly better than repeated Bellman-Ford whenever the graph is not extremely dense, making Johnson's the practical choice for sparse graphs with some negative edges and no negative cycles.

Correctness argument. The correctness of every baseline reduces to the correctness of the underlying SSSP algorithm, applied once per source, plus the observation that shortest-path distances are independent across different choices of source — `δ(s, v)` depends only on `s`, `v`, and the fixed graph, never on which other rows have already been computed. Formally, correctness follows by induction on the outer loop over sources:

• Invariant: after the loop has processed sources `s_1, …, s_k`, rows `s_1` through `s_k` of `D` equal the true shortest-distance rows `δ(s_i, ·)` for each processed `s_i`.
• Base case: before any iteration, no rows are filled, so the invariant holds vacuously.
• Inductive step: processing source `s_{k+1}` calls a correct SSSP subroutine on the unmodified original graph, which by the established correctness of Dijkstra's algorithm or Bellman-Ford, returns exactly `δ(s_{k+1}, v)` for every `v`. This becomes row `s_{k+1}`, extending the invariant.
• Termination: after all `n` sources are processed, every row of `D` is correct, so `D = δ` in full.

For Johnson's algorithm, correctness additionally requires the reweighting lemma proven above: shortest paths under `w'` are exactly the shortest paths under `w`, so running correct Dijkstra on the reweighted graph and undoing the additive correction reproduces the true distances.

Honest tradeoffs. Repeated Dijkstra is fast but silently wrong if negative weights are present — it will return distances that are too large or even miss genuinely shorter paths, without any error signal. Repeated Bellman-Ford is safe and explicitly reports negative cycles but is asymptotically the slowest baseline. Johnson's algorithm recovers speed at the cost of one extra Bellman-Ford pass and a layer of reweighting arithmetic, and it still fails (correctly, with a detected error) if a negative cycle exists. None of the three baselines beats `Θ(V³)` in the worst case for dense graphs, which is precisely the gap that dense-graph dynamic programming techniques are designed to close.

Consider the small directed graph with vertices `{A, B, C, D}` and edges: ``` A → B (weight 3) A → C (weight 8) A → D (weight -4) B → D (weight 1) B → A (weight 4) C → B (weight -5) D → C (weight 2) D → A (weight 6) ``` This graph has a negative edge (`A → D`, weight `-4`, and `C → B`, weight `-5`), so repeated Dijkstra is not safe here; this is exactly the case Bellman-Ford (or Johnson's) must handle. Running Bellman-Ford from each source in turn (each run independently correct by the standard Bellman-Ford proof, since there is no negative cycle in this graph — verify: `A→D→C→B→A = -4+2-5+4 = -3`, a negative cycle... which means this graph in fact does contain a negative cycle reachable from and back to `A`). That detection is itself the pedagogically important outcome: running `BELLMAN-FORD` from source `A` performs its standard `V - 1 = 3` relaxation rounds and then executes one extra check round. Because the cycle `A → D → C → B → A` has total weight `-4 + 2 - 5 + 4 = -3 < 0`, some edge on that cycle still admits a relaxation on the extra round, so Bellman-Ford correctly reports failure for source `A`, and the whole `APSP-BELLMAN-FORD` baseline halts with "negative-weight cycle reachable from A" rather than returning a bogus matrix — this is precisely the safety Dijkstra cannot offer. To see the healthy case, drop the edge `D → A` (weight 6), leaving no cycle. Now Bellman-Ford from source `A` proceeds normally:

Trace of round 2: edge `D → C` relaxes `dist[C]` from `8` to `dist[D] + 2 = -4 + 2 = -2`. Trace of round 3: edge `C → B` relaxes `dist[B]` from `3` to `dist[C] + (-5) = -2 - 5 = -7`. A fourth round changes nothing, confirming convergence with no negative cycle for this source. Repeating this process from `B`, `C`, and `D` and stacking the four resulting distance rows produces the completed distance matrix — the same assembly step shown in the diagram above, now driven by Bellman-Ford instead of Dijkstra because of the negative edges.

The APSP problem sits at the intersection of graph theory and dynamic programming, and its baseline solutions are inherited directly from single-source shortest-path work. Edsger Dijkstra's 1959 algorithm, originally devised for a single source, became the natural per-vertex subroutine once researchers began asking for full distance matrices. Richard Bellman's and Lester Ford's independent formulations of what became the Bellman-Ford algorithm, rooted in dynamic programming over path length, supplied the negative-weight-tolerant alternative. Donald Johnson's 1977 reweighting technique, published specifically to accelerate sparse-graph APSP, is the historical bridge connecting these single-source baselines to the dense dynamic-programming methods that followed, most notably the technique associated with Robert Floyd and Stephen Warshall.

Repeated-SSSP baselines and their assembled distance matrices underpin real infrastructure wherever an all-pairs answer, not a single route, is the actual product. Road-network and mapping services precompute or cache travel-time matrices between hub regions using exactly this repeated-single-source strategy, because most real road networks are sparse (each intersection connects to only a handful of others), making repeated Dijkstra dramatically cheaper than dense-graph alternatives. Internet routing protocols that maintain link-state databases effectively run a Dijkstra-like computation from every router's perspective to build local forwarding tables, an operational echo of the repeated-SSSP idea. Financial systems that detect arbitrage opportunities in currency-exchange graphs rely on Bellman-Ford's negative-cycle detection, since a negative cycle in a log-transformed exchange-rate graph corresponds directly to a profitable arbitrage loop. Compiler and program-analysis tools that compute worst-case or best-case cost bounds between all pairs of program points use the same distance-matrix abstraction, sometimes over sparse control-flow graphs where repeated SSSP is the right tool, and sometimes over dense synthetic graphs where the dynamic-programming methods this article leads into — the Floyd-Warshall Algorithm — take over.

Ask the tutor: How does the Floyd-Warshall algorithm's single evolving matrix beat repeated-SSSP on dense graphs, step by step?