Floyd-Warshall vs Johnson, side by side

The idea: one matrix, two ways to fill it

Both algorithms solve the all-pairs shortest path problem: for a directed weighted graph, fill a V × V matrix D where D[i][j] is the length of the shortest path from i to j. This page runs Floyd-Warshall on the left and Johnson's algorithm on the right, on the same graph, at the same time. Every step does V² operations on each side, so the side that needs less work finishes first. The bars under the lanes count every operation.

Floyd-Warshall: try every vertex as a detour

D starts as the edge weights: 0 on the diagonal, the weight of i→j if that edge exists, ∞ otherwise. Then one vertex k at a time is allowed as a stop on the way.

for k in vertices:
    for i in vertices:
        for j in vertices:
            if D[i][k] + D[k][j] < D[i][j]:
                D[i][j] = D[i][k] + D[k][j]

After round k, D[i][j] is the shortest path that only stops at the vertices up to k. After the last round every stop is allowed, so the matrix is final. On the canvas, row k and column k are blue (they are the only cells the round reads), and the cells that got shorter are orange. The loop does exactly V³ checks. It does not look at the edges at all after the first matrix, so a graph with 7 edges costs the same as one with 30.

Johnson: reweight, then Dijkstra from every vertex

Dijkstra from every vertex would be fast on a sparse graph, but Dijkstra can be wrong when a weight is negative (see Dijkstra vs Bellman-Ford). Johnson first changes the weights so that none is negative, without changing which paths are shortest.

1. Add a new vertex q with a 0-weight edge to every vertex.
2. Run Bellman-Ford from q. The result h(v) is the potential of each vertex (the h column on the canvas). It is 0 or negative.
3. Reweight every edge: w′(u, v) = w(u, v) + h(u) − h(v). The labels in the right lane turn green.
4. Run Dijkstra from every vertex s on w′ and convert back: D[s][v] = d′(s, v) − h(s) + h(v). Each run fills one row of the matrix.

The operations counted on the right are the Bellman-Ford relaxations (V + E per pass), one per reweighted edge, and per Dijkstra run one per out-edge relaxation and one per heap operation (push, decrease-key, pop).

Why reweighting keeps the shortest paths

Add up w′ along any path s = v0 → v1 → … → vk = t. Each inner h appears once with + and once with −, so the sum telescopes: w′(path) = w(path) + h(s) − h(t). Every path from s to t moves by the same amount, so the shortest one stays the shortest.

No w′ is negative because Bellman-Ford's answer obeys the triangle inequality: h(v) ≤ h(u) + w(u, v) for every edge, which is exactly w′(u, v) ≥ 0. Edges on a shortest path from q get w′ = 0, as most edges in the figure do.

Adding the same constant to every edge does not work: a path with more edges gets more of the constant, so the order of the paths changes.

Dense vs sparse: counting the work

Demo	V, E	Floyd-Warshall	Johnson (BF + reweight + relax + heap)	Fewer
1 dense, all ≥ 0	5, 13	125 + 5 = 130	36 + 13 + 65 + 52 = 166	Floyd
2 sparse, all ≥ 0	6, 7	216 + 6 = 222	26 + 7 + 42 + 72 = 147	Johnson
3 sparse, negative edges	6, 7	222	26 + 7 + 42 + 75 = 150	Johnson
4 negative cycle	6, 7	222	91 (7 Bellman-Ford passes of 13)	both detect it
5 dense, negative edges	5, 13	130	36 + 13 + 65 + 58 = 172	Floyd

In general Floyd-Warshall is Θ(V³). Johnson is O(V·E) for Bellman-Ford plus V Dijkstra runs: O(V·E log V) with a binary heap, O(V·E + V² log V) with a Fibonacci heap. When E is close to V², Johnson is no better than V³ and pays for the heap and the extra phases. When E is about V (road maps, most real networks), Johnson is close to V² log V, far below V³.

Negative edges change nothing for Floyd (Demo 1 and Demo 5 both cost 130). For Johnson they only make the potentials non-zero; the heap work changes a little because the Dijkstra runs see different weights.

Negative cycles

In Demo 4 the ring A→B→C→D→E→F→A weighs −1, so there are no shortest paths. Both algorithms notice, in different ways:

• Floyd-Warshall finishes all V³ checks and then reads the diagonal. D[i][i] < 0 means a path from i back to itself with negative weight. Every vertex on the ring turns red.
• Johnson's Bellman-Ford keeps changing h for V passes, so it runs a check pass. An h that can still drop proves a negative cycle, and Johnson stops before any Dijkstra run, after 91 operations.

When to pick which

	Floyd-Warshall	Johnson
Time	Θ(V³)	O(V·E log V) (binary heap)
Extra memory	the matrix only	adjacency lists, h, a heap
Negative edges	fine	fine (after reweighting)
Negative cycle	found at the end (diagonal)	found by Bellman-Ford, before Dijkstra
Code	5 lines	Bellman-Ford + Dijkstra + a heap
Best for	dense or small graphs, matrix input	large sparse graphs

With no negative edges, Johnson's first two phases can be skipped: run Dijkstra from every vertex directly. Pick a graph from the graph menu and press Run Both to race on it.

What the page leaves out

• The real cost of a heap operation is log V, not 1; the page counts each push, decrease-key and pop as one operation, and the priority queue is a scan, not a drawn heap.
• Path reconstruction: a next-hop matrix for Floyd and a parent array per Dijkstra run.
• Floyd's cache-friendly inner loop and its easy parallel and blocked versions, which make it faster in practice than an operation count suggests.
• Early stops: Floyd can skip row i when D[i][k] = ∞, and can stop as soon as a diagonal entry turns negative.
• Undirected graphs, where one negative edge already forms a negative cycle.

References

Johnson's algorithm (Wikipedia)

Floyd-Warshall algorithm (Wikipedia)

Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, J. ACM 24(1), 1977

Sedgewick & Wayne, Algorithms 4th ed., 4.4 Shortest Paths