[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
:::
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$

# 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