Find the shortest path that goes through an even number of red edges

Question

I'm looking for an algorithm for the problem:

"Given an undirected graph with positive weights on its edges and some of the edges are red and some are blue. Describe an algorithm that finds the shortest (lightest) path which includes an even number of red edges, that goes from S to any vertex v."

The solution I thought about was, why not take the original Graph G(V,E) and create (I'm not quite sure if I can say "given" though I think it is) a sub graph which will include only the red edges, let's say Red(V',E'), intersect those two, so now I will have a new graph say G' which includes only the red edges.

And on that graph I will use dijkstra algorithm in order to find the shortest path.

The problem is it can ofc make some edges un-reachable so it will return there's no such path, while there might be a path if added some blue edges. I'm not quite sure how to go around it in order to get the perfect solution.

Answer 1

Here's a nice way to do it. Make two copies of the input graph; call them $A$ and $B$. Now redirect the red edges so that they jump across to the other copy, but leave the blue edges untouched. Any path which starts and ends in $A$ must use an even number of red edges (after using a red edge to get to $B$, it has to use another red edge to get back to $A$). So just run any shortest-paths algorithm on this new "doubled" graph and keep only the shortest paths that both start and end in $A$.

More formally, let $v_A$ and $v_B$ be the two copies of $v$ that appear in $A$ and $B$, respectively. For each original edge $(u,v)$,

• if $(u,v)$ is blue, the new graph will have edges $(u_A, v_A)$ and $(u_B, v_B)$.
• if $(u,v)$ is red, the new graph will have edges $(u_A, v_B)$ and $(u_B, v_A)$.

Note that this transformation only works because the edge weights are positive. Otherwise you could do funky things like traverse a negative edge twice (once within $A$ and once within $B$) to achieve lighter paths in the doubled graph.

Answer 2

An alternative (but essentially equivalent to @SamWestrick's) way of thinking about it is to run Dijkstra on the original graph but keeping track of two parameters for each vertex: the shortest path with an even number of red edges found so far, and the shortest with an odd number.

Here's a more precise description of the algorithm. For each vertex $v$, store values $d_{\mathrm{even}}(v),d_{\mathrm{odd}}(v)$. Initialise these by setting $d_{\mathrm{even}}(S)=0$ and all others (including $d_{\mathrm{odd}}(S)$) to $\infty$. For each vertex have two flags $f_{\mathrm{even}},f_{\mathrm{odd}}$ which determine whether the $d$ values are final or not. Initialise all flags to False.

Now, iteratively do the following. Find a choice of $\mathrm{par}\in\{\mathrm{even},\mathrm{odd}\}$ and $v\in V$ such that $f_{\mathrm{par}}(v)$ is False and $d_{\mathrm{par}}(v)$ is finite and as small as possible (obviously you can use a priority queue to make this efficient). Write $\mathrm{\overline{par}}$ for the opposite of $\mathrm{par}$.

Now set $f_{\mathrm{par}}(v)$ to True. For each $vw\in E$,

• if $vw$ is blue, update $d_{\mathrm{par}}(w)$ to $\min\{d_{\mathrm{par}}(w),d_{\mathrm{par}}(v)+\ell(vw)$;
• if $vw$ is red, update $d_{\mathrm{\overline{par}}}(w)$ to $\min\{d_{\mathrm{\overline{par}}}(w),d_{\mathrm{par}}(v)+\ell(vw)$.

Continue to do this until there are no finite distance values for which the corresponding flag is false. (It may be that there are some values which remain infinite, because there is no path from $S$ of the required parity.)

If you need to find the paths, not just the lengths, you similarly need two different variables keeping track of the predecessor of each vertex, which are updated when the corresponding distances are.

This really is exactly the same as @SamWestrick's elegant answer, though: the "odd" variables are just another way of thinking about the variables for the "B copy" of each vertex.