Can Johnson's algorithm be used with only positive weights?

Yes, although repeated Dijkstra alone may then avoid unnecessary reweighting work.

Does reweighting change reachability?

No. The original edges remain; their weights change, not the existence of routes.

Why add the auxiliary source?

Its zero-weight edges make every original vertex reachable during the potential calculation, including vertices in otherwise disconnected regions.

AI Glossary / Graphs and symbolic AI / Advanced

Johnson's algorithm

Definition

Johnson's algorithm computes shortest paths between all pairs of vertices in a weighted graph. It can accommodate negative edge weights when there is no negative-weight cycle, using a reweighting step that allows repeated applications of Dijkstra's algorithm without changing which paths are shortest.

What it means

An all-pairs problem asks for the best route from every source to every destination, rather than one route from a selected start. Some pairs may be unreachable; that is a valid result, not a zero-distance connection.

Negative weights can represent an abstract cost reduction, even though physical distance is not negative. Standard Dijkstra search requires nonnegative weights. Johnson's algorithm addresses this by changing edge weights in a carefully coordinated way and later recovering distances in the original units.

This entry concerns the all-pairs shortest-path method associated with Donald B. Johnson. It should not be confused with other algorithms bearing the Johnson name, such as methods for enumerating circuits or sequencing jobs.

How it works

Conceptually, add an auxiliary source with a zero-weight edge to every original vertex. Run Bellman-Ford from that source to obtain a potential h(v) for each vertex and detect any negative cycle. If such a cycle is present, the standard procedure cannot provide ordinary finite shortest distances for the full problem.

Replace each edge weight w(u,v) by w'(u,v) = w(u,v) + h(u) − h(v). The potentials make these new weights nonnegative. Remove the auxiliary source and run Dijkstra from each original vertex.

For a path from s to t, the potential adjustments cancel at intermediate vertices. Every path between those same endpoints changes by the same amount, h(s) − h(t), preserving their ranking. Recover an original distance with d(s,t) = d'(s,t) − h(s) + h(t).

Three practical examples

A graph-analysis experiment computes all-pairs costs in a sparse directed network containing negative edges but no negative cycles.
An optimization model uses reweighted shortest-path calculations as part of a larger network computation.
A teaching exercise checks that transforming edge weights preserves competing path order only when the adjustments have the required endpoint structure.

Think of it this way

Think of adjusting route accounts by adding a departure credit and subtracting an arrival credit at each step. At intermediate stops, the two adjustments cancel, leaving only the start and finish adjustments.

The analogy explains why whole-path comparisons survive. The credits are mathematical potentials, not ordinary discounts applied independently to every edge. Arbitrary changes can alter which route is cheapest.

Worked example

Reweighting a three-vertex graph

Consider directed edges A → B with weight 2, B → C with weight −4, and A → C with weight 1. There are no other edges and therefore no cycles. The indirect path A → B → C costs 2 − 4 = −2, less than the direct path's cost 1.

After adding the zero-edge auxiliary source, shortest distances from it give potentials h(A) = 0, h(B) = 0 and h(C) = −4. The transformed edge weights are A → B: 2 + 0 − 0 = 2; B → C: −4 + 0 − (−4) = 0; A → C: 1 + 0 − (−4) = 5.

All are nonnegative. In the transformed graph, the indirect route costs 2 and the direct route costs 5, preserving their ordering. Recovering the indirect original distance gives 2 − h(A) + h(C) = 2 − 0 − 4 = −2.

Simply adding 4 to every edge would instead produce weights 6, 0 and 5. The indirect route would cost 6 while the direct route cost 5, incorrectly reversing the preference. Different path lengths receive different total additions.

Finally, adding an original edge C → A of weight 1 would create a cycle of total weight 2 − 4 + 1 = −1. Repeating that cycle could reduce a walk's cost without limit, invalidating a finite shortest-distance answer for affected pairs.

Illustrative case study

The fictional Willow Graphs team builds an all-pairs cost report from a directed network. Its first workaround for negative edges adds the same constant everywhere, but a small test reveals that this changes the selected route.

Reviewers replace that transformation with an implementation using valid vertex potentials. They compare recovered distances with direct calculations on small graphs and include a negative-cycle test. They also verify how the library represents unreachable pairs and whether it returns paths, distances or both.

Willow documents the meaning of its edge costs before interpreting the report. This fictional case illustrates algorithm validation rather than a claimed improvement in a real routing system.

Common misconceptions and mistakes

Negative edges and negative cycles are the same problem. Individual negative edges are allowed; negative cycles undermine finite shortest-walk costs.
Adding a constant to every edge preserves shortest paths. It can favor paths with fewer edges and change the answer.
Reweighted distances can be reported as original costs. They require the endpoint correction.
An all-pairs routine automatically returns every equally short path. Implementations may return only one representative per reachable pair.

Business use

The method is particularly relevant when many source-destination queries must be answered on a relatively sparse graph. However, computing and storing all-pairs results can be unnecessary when only a few sources are needed.

Assess graph size, density, weight semantics and output requirements before choosing an implementation. The classic O(VE + V² log V) bound assumes suitable priority-queue operations for the repeated Dijkstra runs; other implementations have different bounds. Materializing all distances itself requires up to quadratic output space, and storing explicit routes can require more. Algorithm choice should reflect the required result, not only the input graph's compactness.

Check your understanding

Why does adding 4 to every edge fail in the worked graph?

Answer: The two-edge route receives an addition of 8, while the direct route receives only 4. The unequal adjustments reverse the original route ranking.

Related terms

Dijkstra's algorithm
Sparse graph
All-pairs shortest paths
Bellman-Ford algorithm
negative cycle
vertex potential
reweighting

Learn next

Recover the original B-to-C distance from its transformed distance zero. Then identify which ordered pairs are unreachable in the original three-edge graph and explain why they should not be assigned a distance of zero.

Sources

Johnson's original shortest-path research: https://bohr.wlu.ca/hfan/cp412/references/p1-johnson.pdf

NetworkX documents its Johnson implementation and returned paths: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.johnson.html

Boost's documentation describes its interface and implementation complexity: https://www.boost.org/doc/libs/1_40_0/libs/graph/doc/johnson_all_pairs_shortest.html

The graph arithmetic and Willow Graphs case are original illustrations. The Boost link is versioned historical documentation, not a claim about the latest library interface.

Previous: Job-shop scheduling problem Next: Join Method