4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ A generic version of this question has been posed here, restricting the shortest path to any regular language of colours: cs.stackexchange.com/q/118977/4287 . Of course "even number" is a regular property. $\endgroup$ – Hendrik Jan May 21 at 1:15
  • $\begingroup$ thank you! I would look into it! $\endgroup$ – Ori Moscovitz May 21 at 9:44
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That is genius! thank you! I'm not yet fully understanding the procedure of the redirecting the red edges, but I'll do an example and try to see exactly how to execute it. Thank you so much! $\endgroup$ – Ori Moscovitz May 21 at 9:34
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not sure I followed, If I got that right, what you mean is that I should run the algorithm on the graph and keep the length ("weight") of the shortest path , but how will it know which actual path to return? also, how does it keep track of whether the graph consists and even number of red edges? I would be grateful if you could elaborate And either way, thank you very much for helping! much appreciated :) $\endgroup$ – Ori Moscovitz May 21 at 9:42
  • $\begingroup$ @OriMoscovitz I've updated my answer to clarify how this works. $\endgroup$ – Especially Lime May 21 at 10:23

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.