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)\ge 0$
  • $h(v)$ obtained from running Bellman-Ford
  • $\hat{w}\ge 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

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