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$.

  • 1
    $\begingroup$ 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.) $\endgroup$ – D.W. Apr 6 '16 at 8:04
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Apr 6 '16 at 8:05
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 6 '16 at 8:46
  • $\begingroup$ 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 $\endgroup$ – ebracho Apr 6 '16 at 16:18

I can't comment to this question, so add an answer:

When you use dijkstra's algorithm, in each iteration it finds a new node (name B after A: A---e--->B). If this connecting edge (e) is member of E2, then check the last edge in the path to A. Dismiss the just found node if the last edge is member of E2. then continue the algorithm to finding another node.

  • $\begingroup$ This solution is wrong. The counterexample is a graph with 4 nodes A - D and 4 directed edges (with weight 1): (A, B), (B, C), (A, C), (C, D), the source is A, E2 = {(A, C), (C, D)}, your solution will give +infinity as distance to D. $\endgroup$ – Howdedo Apr 6 '16 at 14:37
  • $\begingroup$ Yes. This point is correct so we can modify last sentence: "remove that edge, then restart the algorithm" $\endgroup$ – moksef Apr 6 '16 at 16:53
  • $\begingroup$ You modified solution still gives +infinity as distance to D on the counterexample above. $\endgroup$ – Howdedo Apr 6 '16 at 17:01
  • $\begingroup$ @Howdedo is D reachable with the conditions? $\endgroup$ – moksef Apr 6 '16 at 17:03
  • $\begingroup$ (A, B), (B, C), (C, D) is a valid path of length 3, isn't it? $\endgroup$ – Howdedo Apr 6 '16 at 17:12

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.