johnson

Johnson’s Algorithm

• Re-weighting technique: If negative edges exist, compute $\hat{w}$ for Dijkstra’s algorithm to work on.
  • $\forall u,v\in V$, $u\stackrel{p}{⇝}v$ is shortest using $w$ if and only if the same applies using $\hat{w}$.
  • $\hat{w}(u,v)\ge 0\forall (u,v)$
• Define $h$ as
  • Introduce a $s\notin V$, so that $w(s,v)=0$ $\forall v\in V$
  • $h(v)=\delta (s,v)$ (using Bellman-Ford algorithm)
• The new weight is given byture
  • $h:V\to \mathbb{R}$ is any mapping
  • $\hat{w}(u,v)=w(u,v)+h(u)-h(v)$
  • So that $\hat{w}(p)=w(p)+h(v_0)-h(v_k)$
• Determining $\hat{w}$ takes $O(VE)$ time.
• Run Dijkstra’s algorithm on each vertex.
• With min-priority-queue in Dijkstra’s algorithm implemented by fibonacci-heap, the runtime is $O(V^2\lg V+VE)$, binary min-heap yields $O(VE\lg V)$.