0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ DFS does not give the shortest path. $\endgroup$ Sep 27 at 21:28
1
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.