Skip to content

Johnson's Algorithm

Summarized notes from Introduction to Algorithms, Chapter 25

  • for sparse graphs this is faster than matrix squaring or Floyd-Warshall
  • output is \(|V| \times |V|\) matrix or indicates there is negative weight cycle
  • internally it uses both Dijkstra's and Bellman-Ford
  • uses adjacency list representation
  • performs reweighting
    • reweighting produces new weight function \(\hat{w}\)
    • \(\hat{w}(u,v) = w(u, v) + h(u) - h(v) \geq 0\)
    • \(h(v)\) obtained from running Bellman-Ford
    • \(\hat{w} \geq 0\) for all edges \((u,v) \in E\)
    • reweighting preserves shortest path in \(G\)
    • once all edge weights are nonnegative run Dijkstra's algorithm
  • Cannot perform reweighting if some vertices are unreachable → add new source \(s\) that has edge weight 0 and connects to every \(v \in V\)

Implementation

img

Complexity

Running Time
\(O(VE)\) Computing \(\hat{w}\)
\(O(V^2\lg V + VE)\) Johnson's algorithm (Fibonacci heap)
\(O(VE\lg V)\) Johnson's algorithm (Binary min heap)

Example

img