0
$\begingroup$

So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non negative) graph $G = (V, E)$, a set of vertices $X \subset V$, and two vertices $s, t \in V \setminus X$. The graph is given with adjacency lists and we can assume that it takes $O(1)$ time to determine if a vertex is in $X$. I'm trying to write an algorithm which can compute the shortest path between $s$ and $t$ in $G$ such that the path includes at most one vertex from $X$ if such a path exists in $O(m + n \log n)$ time. I know that this algorithm would require a modified Dijkstra's algorithm but I'm unsure how to proceed from here.
Could anyone please help me out?

$\endgroup$
1
  • $\begingroup$ indirect? undirected seems much more common. Could anyone please help me out? Think up something. If stuck, present where. $\endgroup$
    – greybeard
    May 8, 2020 at 9:06

1 Answer 1

1
$\begingroup$

Many such problems can be solved by modifying the input instance rather than a known algorithm. In your case you can consider your graph as directed and create a new directed graph $G'$ the is split into $2$ "layers", $A$, and $B$.

Layer $A$ contains a copy of all the vertices in $V$, layer $B$ contains a copy of all the vertices in $V \setminus X$. Given a vertex $v$ let $v_A$ be it's copy in $A$ (if any) and $v_B$ be its copy in $B$ (if any).

The edges of $G'$ are as follows:

  • For each edge $(u,v) \in E$ with $u,v \in V \setminus X$ add to $G'$ the edges $(u_A, v_A)$ and $(u_B, v_B)$ with the same weight as $(u,v)$.

  • For each edge $(u,v) \in E$ with $u \in V \setminus X$, and $v \in X$, add the edge $(u_A, v_A)$ with the same weight as $(u,v)$.

  • For each edge $(u,v) \in E$ with $u \in X$, and $v \in V \setminus X$, add the edge $(u_A, v_B)$ with the same weight as $(u,v)$.

  • Ignore all the edges $(u,v)$ with $u,v \in X$.

  • Finally, for each vertex $v \in V \setminus X$, add the edge $(v_A, v_B)$ with weight $0$.

Your problem now amounts to that of finding the shortest path between $s_A$ and $t_B$ in $G'$, which can be done in $O(m + n \log n)$ time using Dijkstra's algorithm.

$\endgroup$

Your Answer

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

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