yog/pathfinding/johnson

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

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) ≥ 0

This 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

1. Add temporary source: Create new vertex s with 0-weight edges to all vertices
2. Run Bellman-Ford: From s to compute h(v) = distance[v] and detect negative cycles
3. Reweight edges: Set w’(u,v) = w(u,v) + h(u) - h(v) for all edges
4. Run V × Dijkstra: Compute shortest paths on reweighted graph
5. Adjust distances: Set dist(u,v) = dist’(u,v) - h(u) + h(v)

Comparison with Other All-Pairs Algorithms

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

Complexity Analysis

• Bellman-Ford phase: O(VE) - run once
• Dijkstra phase: O(V × (V+E) log V) = O(V² log V + VE) - run V times
• Total: O(V² log V + VE)

For sparse graphs where E = O(V), this is O(V² log V), much better than Floyd-Warshall’s O(V³)!

Negative Cycles

The algorithm detects negative cycles during the Bellman-Ford phase. If a negative cycle exists, the function returns Error(Nil).

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. The algorithm is a brilliant combination of Bellman-Ford’s ability to handle negative weights and Dijkstra’s efficiency with non-negative weights.

References

• Wikipedia: Johnson’s Algorithm
• Johnson’s Original Paper (1977)
• CP-Algorithms: Johnson’s Algorithm
• MIT 6.006: Advanced Shortest Paths

pub fn johnson(
  in graph: model.Graph(n, e),
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_subtract subtract: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> Result(dict.Dict(#(Int, Int), e), Nil)

let result = johnson.johnson(
  in: graph,
  with_zero: 0,
  with_add: int.add,
  with_subtract: int.subtract,
  with_compare: int.compare
)
// => Ok(Dict([#(#(1, 2), 10), #(#(1, 3), 25), ...]))

pub fn johnson_float(
  in graph: model.Graph(n, Float),
) -> Result(dict.Dict(#(Int, Int), Float), Nil)

pub fn johnson_int(
  in graph: model.Graph(n, Int),
) -> Result(dict.Dict(#(Int, Int), Int), Nil)

let result = johnson.johnson_int(graph)
// => Ok(Dict([#(#(1, 2), 10), #(#(1, 3), 25), ...]))