# Shortest path with no two consecutive edges from a certain edge set

Given a graph with nodes $N$ and two sets of edges $E_1$, $E_2$ where no two edges from $E_2$ can be used consecutively, find the shortest path between $n_1, n_2 \in N$.

Is there a smart way to approach this problem other than a brute force search?

Edit: My first attempt involved trying to construct a graph that satisfies the constraint on $E2$. However if a node $n$ is connected with edges in both $E1$ and $E2$, it is impossible to know whether edges in $E2$ will be available on $n$ because it depends on which edge was used to arrive to $n$.

• Yes, there is a smart way. What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you edited the question to show your thoughts and what specifically you could not figure out. (cont.) – D.W. Apr 6 '16 at 8:04
• Also, tell us what you know. Do you know automata theory? What algorithms do you know for computing shortest paths? Finally, do edges have lengths/weights, and if so, are you guaranteed they will all be non-negative? – D.W. Apr 6 '16 at 8:05
• Hint: modify the graph so that paths in the new graph that correspond to such with two consecutive $E_2$-edges in the original graph are prohibitively expensive. – Raphael Apr 6 '16 at 8:46
• I don't think it is possible to generate a static graph that satisfies the non-consecutive constraint on $E2$. This is because the available edges at each node depend on edge used to arrive at that node. If a node connected by edges in both $E1$ and $E2$ it is impossible to know which edges Wil be available before execution – ebracho Apr 6 '16 at 16:18