# Johnson's Algorithm - _Re-weighting_ technique: If negative edges exist, compute $\hat w$ for [[dijkstra|Dijkstra's algorithm]] to work on. - $\forall u, v\in V$, $u\overset p\leadsto 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|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|Dijkstra's algorithm]] on each vertex. - With min-[[priority-queue]] in [[dijkstra|Dijkstra's algorithm]] implemented by [[fibonacci-heap]], the runtime is $O(V^2\lg V+VE)$, binary min-heap yields $O(VE\lg V)$.