patternMinor
Find the shortest path that goes through an even number of red edges
Viewed 0 times
paththenumberedgesshortestthroughredgoesthatfind
Problem
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.
"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.
Solution
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)$,
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.
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.
Context
StackExchange Computer Science Q#125993, answer score: 7
Revisions (0)
No revisions yet.