# Shortest walk with alternating colors in a directed graph

Let $$G$$ be a directed graph such that every edge is colored (red, yellow or green). I want to compute the shortest walk (possibly with repeated vertices) with the restriction that the colors are alternating: red, green, yellow, red, green , ..., etc (the starting color doesn't matter).

So far my idea is to create a new graph $$G'$$ such that is has a copy of each vertex (for each color). Then, by adequately placing every colored edge in the new graph I should be able to just run DFS/BFS in the new graph and get the answer. However, I don't know exactly how to correctly place the edges in the new graph $$G$$, or if this idea works.

• DFS does not give the shortest path. Sep 27, 2021 at 21:28

Let $$G=(V, R \cup G \cup Y)$$, where $$R$$, $$G$$, and $$Y$$ are the sets of red, green, and yellow edges, respectively. I assume you want to find the shortest walk between a pair of given vertices. Let these vertices be $$s$$ and $$t$$.
Create the graph $$G'=(V', E')$$ where $$V' = \{s', t'\} \cup \bigcup\limits_{v \in V} \{v_r, v_g, v_b \}$$ and $$E'= \{ (u_r, v_g) \mid (u,v) \in G \} \cup \{ (u_g, v_y) \mid (u,v) \in Y \} \cup \{ (u_y, v_r) \mid (u,v) \in R \} \cup \{ (s', u_r) \mid u \in V\} \cup \{(v_r, t'), (v_g, t'), (v_y, t') \mid v \in V\}$$.
Let $$\ell$$ be length of the shortest color-alternating path between $$s$$ and $$t$$ in $$G$$, and let $$\ell'$$ be the length the length of the shortest path between $$s'$$ and $$t'$$ in $$G'$$. You have than $$\ell' = \ell + 2$$. Therefore it suffices to find a shortest path from $$s'$$ to $$t'$$ in $$G'$$. This can be done in linear time in the size of $$G'$$ (and $$G$$).