Let $G=(V,E)$ be an undirected graph,such that ever $e\in E$ has a color-blue or red.Given $G$ and some $s,t\in V$ ,find an efficient algorithm that find from all pathes from $s$ to $t$,one with an even amount of red edges,and minimal amount of blue edges.For the part of the even amount of red edges,I know that I can split the vertices,$v$ to $v_o,v_e$ for odd or even amount of red edges till I reached that vertex.But I'm not sure,how to do the part with the blue edges?I could give some weight to the blue edges (and red 0 weight) and use Dijkstra's algorithm,but there is a solution in $O(|E|+|V|)$.Any ideas?
Shortest path with minimal blue edges
algorithms;graphs;graph theory;shortest path