# Shortest paths from $s$ by weight which contain even number of edges

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!

#### Solutions Collecting From Web of "Shortest paths from $s$ by weight which contain even number of edges"

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.

You can do something similar as in this answer: Maintain two separate distances from the source to each vertex, one for paths with an odd number of edges, one for paths with an even number of edges. In each update, use the odd ones to update the even ones and vice versa.