1. The problem

Given a directed weighted graph G = (V, E), we want a matrix D where D[i][j] is the minimum cost from i to j. Its diagonal is 0 when no negative cycle exists; D[i][j] = +∞ when j is unreachable from i. If several edges connect i to j, initialization uses the lightest one.

For one source, start with the preceding guide. For all pairs, graph structure matters: Floyd–Warshall visits every triple of vertices, whereas Johnson takes advantage of sparse edge sets.

2. One graph for both algorithms

Consider four vertices A, B, C, D and the following directed edges. B → C has a negative weight, but cycle B → C → D → B weighs −2 + 2 + 1 = 1: it is not negative.

From A to D, for example, route A → B → C → D weighs 3 − 2 + 2 = 3; A → B → D weighs 8. There is no route from C to A.

3. Floyd–Warshall: allow more intermediates

Number the vertices. D^(k)[i][j] is the minimum cost from i to j when only the first k vertices may appear as internal vertices. An optimal route either avoids k or passes through k; in the latter case it combines routes i → k and k → j.

Initialize the diagonal to 0, edges to their weights and all remaining cells to +∞. The loop over k must be outermost: each phase allows exactly one more possible intermediate. Cells may be updated in the same matrix when no negative cycle exists.

for each i, j: D[i][j] = 0 if i = j; otherwise +∞
for each edge i → j of weight w: D[i][j] = min(D[i][j], w)
for each vertex k:
    for each vertex i:
        for each vertex j:
            if D[i][k] and D[k][j] are finite:
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])

In the example, allowing B as an intermediate reduces A → C from 8 to 3 + (−2) = 1. Then C reduces A → D from 8 to 1 + 2 = 3. Finally D gives C → B at cost 2 + 1 = 3.

To reconstruct routes, also store next[i][j], the first vertex after i on the route to j. Initially next[i][j] = j for a direct edge; when going through k improves D[i][j], set next[i][j] = next[i][k].

4. Johnson: reweight and repeat Dijkstra

Johnson suits sparse graphs that may have negative edges but no negative cycles. Add an artificial vertex q and zero-weight edges q → v to every original vertex. Run Bellman–Ford from q: the resulting distance h(v) is a potential. If Bellman–Ford detects a negative cycle, stop.

The inequality follows from Bellman–Ford: h(v) ≤ h(u) + w(u,v). Reweighted edges are therefore suitable for Dijkstra. This adjustment preserves optimal routes: along any route from s to t, intermediate potentials cancel, so the new weight is the original weight plus h(s) − h(t).

add q and zero-weight edges q → v
h = Bellman–Ford(G with q, source q)
if there is a negative cycle: stop
for every edge u → v: w′(u,v) = w(u,v) + h(u) − h(v)
for each original source s:
    δ′ = Dijkstra(G with weights w′, source s)
    for each reachable t: D[s][t] = δ′(s,t) − h(s) + h(t)
    for each unreachable t: D[s][t] = +∞

For the example graph, Bellman–Ford from q gives h(A) = 0, h(B) = 0, h(C) = −2, h(D) = 0. Reweighted edges A → B, A → C, B → C, B → D, C → D, D → B have weights 3, 10, 0, 5, 0, 1 respectively: none is negative.

Dijkstra from A finds δ′(A,C) = 3 via B; restoring the potential gives D[A][C] = 3 − 0 + (−2) = 1. From D it finds δ′(D,C) = 1 via B; the original cost is 1 − 0 + (−2) = −1. These match the Floyd–Warshall matrix.

5. Negative cycles

Floyd–Warshall detects a negative cycle if, at the end, some D[k][k] < 0. For a pair (i, j), the value is −∞ if some such k has finite D[i][k] and D[k][j]: the route can reach the cycle and then j. Checking the diagonal alone does not identify every affected pair.

Johnson finds any negative cycle in the graph because q reaches every vertex. It then does not produce an ordinary finite-distance matrix. If unaffected pairs are needed, use the reachability check through negative cycles after Floyd–Warshall.

In the example, changing D → B from 1 to −1 makes B → C → D → B a cycle of weight −1. A → D becomes −∞; C → A remains +∞ because A cannot be reached from C.

6. Choice and complexity

The Johnson and Dijkstra bounds assume a simple graph, adjacency lists and a binary heap; they include the output matrix. Johnson also runs an initial Bellman–Ford, whose cost is covered by the displayed bound. If rows are consumed one at a time, Johnson’s auxiliary memory drops to O(|V| + |E|). Floyd–Warshall uses O(|V|²) even with a next-vertex matrix.

7. Mistakes and exercises

• Reordering Floyd–Warshall loops: k must remain outermost because it identifies which intermedi are allowed in each phase.
• Running Dijkstra on Johnson’s original negative weights: first reweight edges using the potentials.
• Forgetting the final correction: distances with reweighted edges are not the original distances.
• Confusing +∞ with a negative cycle: it means unreachable; −∞ means the cost is unbounded below.