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

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.

• indirect? undirected seems much more common. Could anyone please help me out? Think up something. If stuck, present where. – greybeard May 8 '20 at 9:06

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.