Johnson's algorithm for all-pairs shortest paths in weighted graphs with negative edge weights.
Johnson's algorithm efficiently computes shortest paths between all pairs of nodes in sparse graphs, even when edges have negative weights (but no negative cycles). It combines Bellman-Ford and Dijkstra's algorithms with a reweighting technique.
Algorithm
| Algorithm | Function | Complexity | Best For |
|---|---|---|---|
| Johnson's | johnson/5 | O(V² log V + VE) | Sparse graphs with negative weights |
Key Concepts
- Reweighting: Transform negative weights to non-negative while preserving shortest paths
- Bellman-Ford Phase: Compute reweighting function and detect negative cycles
- Dijkstra Phase: Run Dijkstra from each vertex on reweighted graph
- Distance Adjustment: Transform reweighted distances back to original weights
How Reweighting Works
The algorithm computes a potential function h(v) for each vertex such that:
w'(u,v) = w(u,v) + h(u) - h(v) ≥ 0This transformation preserves shortest paths because for any path p = v₁→v₂→...→vₖ:
w'(p) = w(p) + h(v₁) - h(vₖ)So the relative ordering of path weights remains the same!
The Algorithm Steps
- Add temporary source: Create new vertex
swith 0-weight edges to all vertices - Run Bellman-Ford: From
sto compute h(v) = distance[v] and detect negative cycles - Reweight edges: Set w'(u,v) = w(u,v) + h(u) - h(v) for all edges
- Run V × Dijkstra: Compute shortest paths on reweighted graph
- Adjust distances: Set dist(u,v) = dist'(u,v) - h(u) + h(v)
Comparison with Other All-Pairs Algorithms
| Approach | Complexity | Best For |
|---|---|---|
| Floyd-Warshall | O(V³) | Dense graphs (E ≈ V²) |
| Johnson's | O(V² log V + VE) | Sparse graphs (E ≪ V²) |
| V × Dijkstra | O(V(V+E) log V) | Sparse graphs, non-negative weights only |
Rule of thumb:
- Use Johnson's for sparse graphs with negative weights
- Use Floyd-Warshall for dense graphs or when simplicity matters
- Use V × Dijkstra for sparse graphs with only non-negative weights
Negative Cycles
The algorithm detects negative cycles during the Bellman-Ford phase.
If a negative cycle exists, the function returns {:error, :negative_cycle}.
Use Cases
- Sparse road networks: Computing all-pairs distances with tolls/credits
- Currency arbitrage: Finding profitable exchange cycles
- Network routing: Precomputing routing tables with various costs
- Game AI: Pathfinding in large sparse maps with varied terrain costs
History
Published by Donald B. Johnson in 1977.
References
Summary
Types
Distance matrix: map from {from, to} tuple to distance.
Functions
Computes all-pairs shortest paths using Johnson's algorithm.
Types
@type distance_matrix() :: %{required({Yog.node_id(), Yog.node_id()}) => any()}
Distance matrix: map from {from, to} tuple to distance.
Functions
@spec johnson( Yog.graph(), any(), (any(), any() -> any()), (any(), any() -> any()), (any(), any() -> :lt | :eq | :gt) ) :: {:ok, distance_matrix()} | {:error, :negative_cycle}
Computes all-pairs shortest paths using Johnson's algorithm.
Time Complexity: O(V² log V + VE)
Returns {:ok, distance_matrix} on success, or {:error, :negative_cycle}
if a negative cycle is detected.
Parameters
graph- The graph to analyzezero- Identity element for additionadd- Function to add two weightssubtract- Function to subtract two weightscompare- Function to compare two weights
Examples
# Graph with negative weights (but no negative cycles)
iex> graph = Yog.directed()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge!(from: 1, to: 2, with: 4)
...> |> Yog.add_edge!(from: 2, to: 3, with: -3)
...> |> Yog.add_edge!(from: 1, to: 3, with: 10)
iex> compare = &Yog.Utils.compare/2
iex> {:ok, distances} = Yog.Pathfinding.Johnson.johnson(graph, 0, &(&1 + &2), &(&1 - &2), compare)
iex> # Shortest path from 1 to 3 should be 1->2->3 = 1, not direct 10
...> distances[{1, 3}]
1
# Negative cycle detection
iex> bad_graph = Yog.directed()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_edge!(from: 1, to: 2, with: 1)
...> |> Yog.add_edge!(from: 2, to: 1, with: -3)
iex> compare = &Yog.Utils.compare/2
iex> Yog.Pathfinding.Johnson.johnson(bad_graph, 0, &(&1 + &2), &(&1 - &2), compare)
{:error, :negative_cycle}