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!
 A: 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.
A: 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.
A: The answers from @Belgi and @joriki are erroneous because they only find the shortest trail (i.e it can go through a vertex more than once): The shortest path in the bipartite graph can pass through both a node in $V$ and the corresponding node in $V'$.
The problem of the shortest even path in directed graphs is in fact $\mathcal{NP}$-hard but is polynomial in undirected graphs. See:
LaPaugh, Andrea S.; Papadimitriou, Christos H., The even-path problem for graphs and digraphs, Networks 14, 507-513 (1984). ZBL0552.68059.
