Find shortest path of R,G,B Graph Let $G=(V,E)$ be a directed graph, $ω:E→\mathbb{R}$ a weight function, and $s,t\in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Each edge has the color R or G or B. Find the shortest path under the condition:


we can use green edge after using at least one red edge  
we can use blue edge after using at least one red edge and at least one green edge.  


The shortest path do not have to be colorful.
Let's look at the form of the allowed paths. As a regular expression, it looks like:

$$r^*\ |\ r(r|g)^*\ |\ rr^*g(r|g|b)^*$$

We can test the three cases separately and then choose the shortest path found among the three cases.

The first case is easy: just remove all the green and blue edges and then find the shortest path from $s$ to $t$ as normal. Of course, there may not be a path from $s$ to $t$ in this red-only subgraph; if this happens, we can say the distance for this case is $\infty$.

For the second case, start with the original graph and remove all the blue edges, leaving only red and green edges. Then add a new vertex $s^\prime$, which has a directed edge to each vertex $v$ exactly when there is a red edge from $s$ to $v$ in the original graph. Then check for the shortest path from $s^\prime$ to $t$ in this modified graph; this corresponds exactly to the shortest path from $s$ to $t$ in the original graph that has the form $r(r|g)^*$. Again, if no such path exists, we can return $\infty$ from this case.

See if you can figure out the third case now. 

I have asked and answered a more general form of this question here.