1
$\begingroup$

I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, t but the path should also contain two given arcs in a sequence. Say we are given arcs a1, a2, we want to find a simple shortest path that goes from s to tail of a1 and from head of a1 to tail of a2 and then from head of a2 to the sink t. I was wondering if there is any elegant algorithm or even a mixed integer programming approach to solve this problem.

I am currently planning to modify Dijkstras algorithm to forbid certain nodes that have been previously added to the path.

Edit: I want the whole path from $s$ to $t$ to be simple.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

Let arc $a1$ be $(u_1, v_1)$ and $a2$ be $(u_2, v_2)$. As you mentioned in your question, you want to find a simple shortest path that:

  1. Goes from source $s$ to $u_1$
  2. From $v_1$ to $u_2$
  3. From $v_2$ to the sink $t$.

As you DAG has only positive weights, I think you should find the shortest paths for all three cases (using Dijkstra or any other algorithm) and join them together to get the shortest path from $s$ to $t$ satisfying the given constraints.

EDIT: As the question is for Simple Path, I will refer you to this: http://math.mit.edu/~goemans/18438S12/lec22.pdf.

I am quoting a few important points here:

  1. We first note that the arc-disjoint path problem, and the vertex-disjoint path problem in a directed graph are equivalent - i.e. we can give a polynomial-time reduction in either direction.

  2. Undirected Edge Disjoint Paths. In the case of fixed k (i.e. there are k source-sink pairs), there is a polynomial-time algorithm to decide if there are edge-disjoint paths connecting each $s_i$,$t_i$ pair. This result follows from the Graph Minor Project of Robertson and Seymour (1995), and is very involved. Yet for super-constant k, the undirected edge-disjoint paths problem is NP-complete. 22-1

  3. Directed Arc Disjoint Paths. Even for $k = 2$ it is NP-complete to determine if there are arc-disjoint paths P1, P2 connecting s1, t1 and s2, t2. In fact, we can even choose s1 = t2 and s2 = t1 and this problem still remains NP-complete.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I tried this but there are reverse arcs and sometimes the path from $v_1$ to $u_2$ can visit the already visited vertex again. $\endgroup$
    – ceej10
    Apr 22, 2020 at 10:19
  • $\begingroup$ Why do you think we shouldn't allow revisiting a vertex? You didn't mention that in your original question. I know that in a shortest path a vertex is never repeated, but that is because we don't have the required condition of using a given arc. $\endgroup$
    – prime_hit
    Apr 22, 2020 at 10:23
  • $\begingroup$ Sorry should have been more clear. I wanted the whole path from $s$ to $t$ to be simple . $\endgroup$
    – ceej10
    Apr 22, 2020 at 10:25
  • $\begingroup$ @prime_hit: Actually he did mention that in the question. That's what a simple path is. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Apr 22, 2020 at 10:26
  • $\begingroup$ @BlueRaja-DannyPflughoeft True, my bad. I will update my answer. $\endgroup$
    – prime_hit
    Apr 22, 2020 at 10:28
0
$\begingroup$

If you subdivide your two must-include edges creating a node right in the middle of the edge, you have an instance of requiring a simple path with two must-include nodes. The general problem (requiring $k$ must-include nodes) is studied here:

https://utd-ir.tdl.org/bitstream/handle/10735.1/2637/ECS-TR-EE-Vardhan-310316.85.pdf?sequence=7&isAllowed=y

(2009 paper, H. Vardhan et al, 9 authors in total)

Improve this answer
$\endgroup$

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.