---
# System prepended metadata

title: Johnoson's Algotithm for Sparse Graphs
tags: [Data Structures and Algorithms]

---

[Home Page - Data Structures and Algorithms](/@chun61205/Data-Structures-and-Algorithms)
[toc]

Given a directed, weighted graph $G=(V,E)$.
# Algorithm
## Reweight
We want ot compute a new weight function $\hat{w}$ such that
1. For all $u,v\in V$, $p$ is a shortest path $u\rightsquigarrow v$ using $w$ if and only if $p$ is a shortest path $u\rightsquigarrow v$ using $\hat{w}$.
2. For all $(u,v)\in E$, $\hat{w}(u,v)\geq0$
### How to reweight?
Let $h$ be any function such that $h:V\to R$.
For all $(u,v)\in E$, define
$$
\hat{w}(u,v)=w(u,v)+h(u)-h(v)
$$
Let $p=[v_0,v_1,...,v_k]$ be any path $v_0\rightsquigarrow v_k$.
1. $p$ is a shortest path $v_0\rightsquigarrow v_k$ with $w$ if and only if $p$ is a shortest path $v_0\rightsquigarrow v_k$ with $\hat{w}$.
2. $G$ has has a negative-weight cycle with weight $w$ iff $G$ has a negative-weight cycle with weight $\hat{w}$.

* Proof
    1. Show that $\hat{w}(p)=w(p)+h(v_0)-h_(v_k)$
        $$
        \begin{aligned}
        \hat{w}(p)&=\sum_{i=1}^k\hat{w}(v_{i-1},v_i)\\
        &=\sum_{i=1}^k(w(v_{i-1},v_i)+h(v_0)-h_{v_i})\\
        &=\sum_{i=1}^kw(v_{i-1},v_i)+h(v_0-h(v_k))\\
        &=w(p)+h(v_0)-h(v_K)
        \end{aligned}
        $$
        Since $h(v_0)$ and $h(v_k)$ don't depend on the path from $v_0$ to $v_k$, if one path $v_0\rightsquigarrow v_k$ is shorter than another with $w$, it's also shorter with $\hat{w}$
    2. Show that there exists a negative-weight cycle with $w$ if and only if there exists a negative-weight cycle with $\hat{w}$
        Let a cycle $C=[v_0,v_1,...,v_k]$, where $v_0=v_k$
        $$
        \hat{w}(C)=w(C)+h(v_0)-h(v_k)=w(C)
        $$
        Therefore, $C$ has a negative-weight cycle with $w$ if and only if it has a negative-weight cycle with $\hat{w}$
    3. How to decide $h$?
        :::info
        ![](https://hackmd.io/_uploads/rkdb873Uh.png)
        :::
        Let
        1. $G'=(V',E')$
        2. $V'=V\cup\{s\}$, where $s$ is a new vertex.
        3. $E'=E\cup\{(s,v):v\in V\}$
        4. $w(s,v)=0$ for all $v\in V$

        Since no edges enter $s$, $G'$ has the same set of cycles as $G$.
        Define $h(v)=\delta(s,v)$ for all $v\in V$
        $\delta(s,v)\leq\delta(s,u)+w(u,v)\\\Rightarrow h(v)\leq h(u)+w(u,v)\\\Rightarrow w(u,v)+h(u)-h(v)\geq0$
        
![](https://hackmd.io/_uploads/ByXZ5E58h.png)
# Analysis
## Time Complexity
1. Compute $G'$: $\Theta(V+E)$
2. `BELLMAN-FORD`: $o(VE)$
3. Compute $\hat{w}$: $\Theta(E)$
4. Run Dikstra's algorithm using Fibonacci heap: $O(VlogV+E)$ for $|V|$ times
5. Compute $D$ matrix: $O(V^2)$

Overall: $O(V^2logV+VE)$

**References**
* NCKUCSIE 1112_F721300 Algorithms
* Introduction to Algorithms (Third Edition), T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein