Create an algorithm for computing the shortest path in O(m + nlogn)

Question

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?

• greybeard: indirect? undirected seems much more common. Could anyone please help me out? Think up something. If stuck, present where.

Answer 1

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.