-2
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 16:18

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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, 2016 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, 2016 at 16:53
  • $\begingroup$ You modified solution still gives +infinity as distance to D on the counterexample above. $\endgroup$
    – Howdedo
    Apr 6, 2016 at 17:01
  • $\begingroup$ @Howdedo is D reachable with the conditions? $\endgroup$
    – moksef
    Apr 6, 2016 at 17:03
  • $\begingroup$ (A, B), (B, C), (C, D) is a valid path of length 3, isn't it? $\endgroup$
    – Howdedo
    Apr 6, 2016 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.