Shortest path by colored flips

Question

Let $G=(V,E)$ be a directed graph,and every edge in $E$ has a color-red or blue. Describe an efficient algorithm,that given such colored grahp $G$,and two $s,t\in V$,will find the shortest directed path from $s$ to $t$,such that in that path the amount of color flips is minimal,or will announce that there isn't such.

My idea-modify the BFS algorithm,such that $d[v]$ will be now the amount color flips in the shortest path from $s$ to $v$.

Can it work that way?

**EDIT:**Assuming also that I remember the last color of the last edge visited

Answer 1

No, it can't work. Evidently you need some information about color of the last edge visited. And here is some problem. Let see the following example: $$\begin{matrix} 1 & \color{red}\rightarrow & 2 \\ \color{blue}\downarrow & & \color{blue}\downarrow \\ 3 & \color{red}\rightarrow & 4 & \color{red}\rightarrow & 5 \end{matrix} $$ Suppose you are moving from vertex to vertex 5. Then you have $d_1 = 0$, $d_2 = 0$, $d_3 = 0$, $d_4 = 1$. And now you need to know that you can reach vertex $4$ for one flip with last edge red. If you mark vertex $4$ as first time reached with blue color, then you'll have wrong answer for vertex $5$.

To get right solution you can just split each vertex $v$ into two copies $v_r$ and $v_b$. Each red edge $\{\,u, v\,\}$ becomes an edge $\{\,u_r, v_r\,\}$, while each blue edge $\{\,u, v\,\}$ becomes an edge $\{\,u_b, v_b\,\}$. All these edges have weight 0. Also there are edges $\{\,v_r, v_b\,\}$ of weight 1 for each vertex $v$. Now use BFS on either deque or two queues to find the shortest path from both copies of starting vertex to both copies of finish vertex.