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. Interactive lab

Edit the edges and compare both algorithms on the same graph. Step through Floyd–Warshall matrix checks, or follow Johnson’s potentials and each Dijkstra search. Choose a pair to see its reconstructed route; distances are provisional during the animation. The lab uses explicit scans for Dijkstra; the complexity table assumes a priority queue.

6. 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.

7. 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.

8. 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.