Johnson all-pairs shortest paths: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

Johnson all-pairs shortest paths example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. 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
      ]
    }
  2. 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
      ]
    }
  3. 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
      ]
    }
  4. 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
      ]
    }
  5. 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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

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