# Shortest path with minimal blue edges

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?

• If you're thinking Dijkstra's algorithm, then you must think this is a shortest-paths problem. Do you know any other algorithms for finding shortest paths? – D.W. Apr 16 '17 at 17:25
• @D.W. You mean like BFS,DFS? – ChikChak Apr 16 '17 at 17:28
• This is your exercise, so I'm going to let you figure out how to solve it. I encourage you to spend some more time on it and see what you can come up with. – D.W. Apr 16 '17 at 17:30
• @D.W. ok,but will you give me a hint?do I need to modify BFS/DFS in the solution? – ChikChak Apr 16 '17 at 18:14
• I think D.W. is pushing you in the right direction. Do not think what to do at first glance (e.g., whether to modify BFS/DFS or any other algorithm). Instead recognize the key components of your problem to figure out how to do it. D.W. already told you an important one: according to your intuition if you use weights then this problem can be seen as a Shortest Path Problem (SPP). Note however, there is an additional component, and it is that candidates are constrained to have an even amount of red edges. Question is: what SPP algorithm(s) you know that could handle constraints, and how? – Carlos Linares López Apr 16 '17 at 23:11