Published by Dimitris Kougioumtzis · Updated
Use Bellman-Ford potentials to remove negative weights, then dense Dijkstra from every vertex. Detect negative cycles anywhere in the graph.
Initialize every Bellman-Ford potential to zero, equivalent to adding a zero-cost super-source. Reweight each edge by w(u,v)+h(u)-h(v), run Dijkstra from every source, then undo the potential adjustment.
When to use Johnson all-pairs shortest paths
All-pairs shortest paths in directed graphs that contain negative edges but no negative cycles.
Choosing an alternative
Floyd-Warshall updates all pairs through successive intermediate vertices. Johnson enables faster sparse-graph variants by reusing Dijkstra after a single potential computation.
Worked example: input and state changes
Example input
0,1,-3;1,2,2;0,2,8;2,3,0;3,1,3
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Implicit super-source has zero edges to every vertex; all potentials start at zero.
State at this checkpoint
{ "values": [ "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity" ], "active": [], "kind": "matrix", "columns": 4, "potentials": [ 0, 0, 0, 0 ] }Step 5: Settle 0 for source 0; restore original distances with potentials.
State at this checkpoint
{ "values": [ 0, -3, 8, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity" ], "active": [ 0 ], "kind": "matrix", "columns": 4, "potentials": [ 0, -3, -1, -1 ] }Step 11: Settle 2 for source 1; restore original distances with potentials.
State at this checkpoint
{ "values": [ 0, -3, -1, -1, "infinity", 0, 2, 2, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity" ], "active": [ 6 ], "kind": "matrix", "columns": 4, "potentials": [ 0, -3, -1, -1 ] }Step 16: Settle 1 for source 2; restore original distances with potentials.
State at this checkpoint
{ "values": [ 0, -3, -1, -1, "infinity", 0, 2, 2, "infinity", 3, 0, 0, "infinity", "infinity", "infinity", "infinity" ], "active": [ 9 ], "kind": "matrix", "columns": 4, "potentials": [ 0, -3, -1, -1 ] }Step 21: All-pairs shortest distances complete; infinity denotes an unreachable destination.
State at this checkpoint
{ "values": [ 0, -3, -1, -1, "infinity", 0, 2, 2, "infinity", 3, 0, 0, "infinity", 3, 5, 0 ], "active": [], "kind": "matrix", "columns": 4, "potentials": [ 0, -3, -1, -1 ], "result": 0, "distances": [ 0, -3, -1, -1, 1000000, 0, 2, 2, 1000000, 3, 0, 0, 1000000, 3, 5, 0 ] }
Expected final state
All-pairs shortest distances complete; infinity denotes an unreachable destination.
Complexity and input bounds
Family: Graphs. Time complexity: O(V^3 + VE).
Implementation detail: The teaching version uses dense matrices and linear minimum selection, so O(V^3 + VE) time is the appropriate bound; it does not claim the sparse-graph heap bound. Downloads return -1 on a negative cycle or 0 on success, writing distances row-major with 1000000 for unreachable pairs.
Space complexity: O(V^2) auxiliary space for the reweighted matrix, excluding the O(V^2) distance output and recorded snapshots.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Directed source,target,weight triples separated by semicolons; vertices 0..7; weights -99..99; at most 16 edges.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
A negative cycle in any component invalidates the result, even when unreachable from vertex 0. Zero-weight edges are valid. Never run ordinary Dijkstra directly on negative weights.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | // Directed graph: 1..8 vertices, 0..16 edges; endpoints in range; integer weights -99..99. Output capacity at least vertices*vertices. Returns -1 on any negative cycle (output unspecified); otherwise returns 0 and writes original all-pairs distances row-major, with 1000000 for unreachable pairs and zero diagonal. Dense Dijkstra gives O(V^3 + VE) time; O(V^2) auxiliary space excluding output. Parallel edges, zero weights, self-loops and disconnected vertices are supported. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(from, to, weight, edges, vertices, output) { let potential = Array(256).fill(0); let dist = Array(256).fill(0); let done = Array(256).fill(0); let reweighted = Array(256).fill(0); let changed = 0; let u = 0; let v = 0; let cost = 0; for (let pass = 0; pass < vertices; pass++) { changed = 0; for (let i = 0; i < edges; i++) { if (potential[to[i]] > potential[from[i]] + weight[i]) { potential[to[i]] = potential[from[i]] + weight[i]; changed = 1; } } if (changed == 0) { break; } if (pass == vertices - 1) { return -1; } } for (let i = 0; i < vertices * vertices; i++) { reweighted[i] = 1000000; } for (let i = 0; i < edges; i++) { u = from[i]; v = to[i]; cost = weight[i] + potential[u] - potential[v]; if (reweighted[u * vertices + v] > cost) { reweighted[u * vertices + v] = cost; } } for (let source = 0; source < vertices; source++) { for (v = 0; v < vertices; v++) { dist[v] = 1000000; done[v] = 0; } dist[source] = 0; for (let step = 0; step < vertices; step++) { u = -1; for (v = 0; v < vertices; v++) { if (done[v] == 0 && (u < 0 || dist[v] < dist[u])) { u = v; } } if (u < 0 || dist[u] == 1000000) { break; } done[u] = 1; for (v = 0; v < vertices; v++) { cost = reweighted[u * vertices + v]; if (cost < 1000000) { if (dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; } } } } for (v = 0; v < vertices; v++) { output[source * vertices + v] = 1000000; if (dist[v] < 1000000) { output[source * vertices + v] = dist[v] - potential[source] + potential[v]; } } } return 0; } |
Source
Primary research source for the method. The playground uses a bounded dense-matrix teaching implementation; its guide states the resulting complexity separately from sparse adjacency-list variants.
- Efficient Algorithms for Shortest Paths in Sparse Networks
Donald B. Johnson (1977). Original research paper.