Given a directed graph $G=(V,E)$, and a vertex $s\in V$, for every edge there's an integer weight $w(e)$ (positive or negative), I need to find an algorithm such that for every vertex $v \in V$ it finds the shortest path (by weights) which contains an even number of edges. (I can assume it doesn't have a negative cycles).
Obviously I need to use Bellman-Ford with complexity of $O(|V||E|)$, but how do I manipulate it in such way that the paths will contain an even number of edges?
Thanks!
Best Answer
Create a new graph with the vertices being $V\cup V'$ where $V'$ is a replicate of the vertices of $G$ (meaning $\mid V'\mid=\mid V\mid$ and the sets are disjoint).
The edges are: $$e'=(i,j')\in E' \iff e=(i,j)\in E$$ $$e'=(i',j)\in E' \iff e=(i,j)\in E $$
(there are no edges of the form $(i,j),(i',j')$.
The weights are $w'((i,j'))=w'((i',j))=w((i,j))$.
Now, any path from $i$ to $j$ must be of even length (paths of odd length end up in $V'$ and not in $V$).
Now you can use Bellman-Ford.