Shortest path from $s$ to $v$ in unweighted simple directed graphs

Question

Let $G=(V,E)$ be an unweighted simple directed graph. Some of the edges are colored red. Let $E'⊆E$ denote the set of red edges. Given a vertex $s∈V$,suggest an efficient algorithm for finding the length of a shortest path from $s$ to every other vertex in the graph, fulfilling the following condition: the path includes at most two red edges. In other words, every $v∈V$ should be labeled with the length of a shortest path from $s$ to $v$ in which there are at most two edges from $E'$ and any number of edges from $E\backslash E'$.

Answer 1

Create a new graph $G' = (W,F)$ as follows:

• For every every $v\in V$, create three vertices $v_0,v_1,v_2$ in $W$. The index $i$ in $v_i$ represents the fact that any path to this vertex uses exactly $i$ red edges.
• For every edge $(u,v)\in E\setminus E'$, create the edges $(u_0,v_0)$, $(u_1,v_1)$ and $(u_2,v_2)$ in $F$.
• For every edge $(u,v)\in E'$, create the edges $(u_0,v_1)$, $(u_1,v_2)$ in $F$.

Now you just have to compute the length of the shortest path from $s_0$ to any other vertex in your new graph $G'$ (if the vertex is unreachable then let this distance be $+\infty$). The length of the corresponding shortest path from $s$ to $v$ in $G$ is then the minimum of the lengths to $v_0,v_1$ and $v_2$.

Answer 2

The problem you posted is a single source shortest-path which given a graph G(V, E) and a designated vertex $s\in V$, requires computing the shortest path from $s$ to all vertices $v\in V$ where the cost of a path $\omega(\pi)$ is defined as the sum of all edge costs in $\pi$.

For this specific problem in particular, I would highly recommend a straight application of Dijkstra's algorithm. Indeed, there is no need to replicate vertices and the problem can be optimally solved over the original graph without modifications. There is, however, a subtle question to take into account ...

There are two necessary modifications over the original implementation of Dijkstra's algorithm (here I'm referring to the implementation in the link given above under section "Practical optimizations and infinite graphs"):

1. For each vertex generated, keep track of the number of red edges that were taken in the path from $s$ to it. If a descendant is generated with a number of red edges that exceeds your threshold (2 in your case) then dismiss it, i.e., instead of if n not in explored (before last line in the pseudocode referred to above) you should say if n not in explored and number(red_edges)<=2

2. However, duplicate detection (which is implemented in if n not in explored) is tricky here: assume you find a shortest path from $s$ to a node $v$ after expanding 2 red edges. As Dijkstra's guarantees that this is the optimal path from $s$ to $v$ you certainly accept it, but it might happen that this path can not be extended to reach another vertex $u\in V$ because it is necessary to traverse another red edge. Hence, if $v$ is found again, it should be added to OPEN (called frontier in the pseudocode) even if the new path has a greater cost if and only if the number of red edges of the new path is less than the number of red edges traversed in the optimal path. This way, if the optimal path can not be extended to reach the vertex $u$ there is a chance for this sub-optimal path to reach it.

If memory is an issue for you, then the same problem can be solved using depth-first search strategies. Let me know if you are interested in these ...

Hope this helps,

PS - As you are a new contributor let me please emphasize the following: Tassle's response is definitely right and mine ain't better than his/hers. In addition (s)he was first to provide a correct answer to your problem, so please follow his advice and do not forget to accept her/his answer as it certainly closes the question. That is typical in stack exchange and it is a way to acknowledge the contributions of unknown people.