ExtendedSource checked

Johnson's Algorithm

Finds all-pairs shortest paths in sparse graphs by reweighting edges.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Advanced
Family: All-Pairs Shortest Path
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 7
Code example: Not ready
Visualization: Ready

Overview

Johnson's Algorithm uses Bellman-Ford to remove negative weights, then runs Dijkstra from each node.

Core Concepts

distance relaxationall-pairs tableedge weightsgraph representationall-pairs shortest pathroute costfrontier expansionpath reconstruction

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(VE + V^2 log V)

Average

O(VE log V)

Worst

O(VE + V^2 log V)

Space

O(V^2)

When to Use

Use Johnson's Algorithm when you need to reweight edges to be nonnegative.
Use it for sparse all-pairs shortest paths with inputs like weighted directed graph.
Use it when routes have explicit movement rules, costs, obstacles, or graph edges.
Use it when the All-Pairs Shortest Path tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when edge costs or movement constraints do not match the algorithm's assumptions.
Avoid it when O(VE + V^2 log V) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not all-pairs shortest path distances.

What It Does

Reweights edges to be nonnegative
Runs single-source shortest paths from every node

Use Cases

Sparse all-pairs shortest paths
Graphs with some negative edges
Network analysis

Inputs

Weighted directed graph

Outputs

All-pairs shortest path distances

Key Formulas (1)

Reweighted edge

weight'(u, v) = weight(u, v) + h_[u] − h_[v]

weight'(u, v) = weight(u, v) + h[u] - h[v]

Transforms edge weights so Dijkstra's Algorithm can be used from each source.

Pseudocode

1.Add a temporary source connected to every node
2.Run Bellman-Ford to compute potentials
3.Reweight every edge to remove negative weights
4.Run Dijkstra from each original node
5.Convert distances back to original weights

Canonical Example

Input: edges = A-B: 1, B-C: 2, A-C: 5; start = A; goal = C
Output: path = A -> B -> C, cost = 3
Explanation: Johnson's Algorithm: The algorithm compares route costs and selects the cheaper path through B.

Implementation Notes

Keep the input contract explicit: Weighted directed graph.
Use this step as the implementation spine: Add a temporary source connected to every node.
Then preserve the next state change: Run Bellman-Ford to compute potentials.
Keep node ids, edge direction, and visited state explicit in the implementation.
Store predecessor links if the final path is needed, not just the final distance.

Common Pitfalls

A negative cycle makes the shortest path problem undefined.
Not defining directed versus undirected edges clearly can change the result.
Treating a visited node as final before its best known cost is actually settled.
Returning all-pairs shortest path distances without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show edge weights being adjusted before repeated shortest-path runs.

Step 1 of 5: Add a temporary source connected to every node

reweighted-graph

Notes

Johnson's Algorithm operates in O(VE log V) time and O(V^2) space within the All-Pairs Shortest Path family. Key governing relation: weight'(u, v) = weight(u, v) + h[u] - h[v]. Often compared with Bellman-Ford and Dijkstra's Algorithm.