Shortest path algorithm where the path can travel through at most 2 vertices in X ⊂ V

Question

I am trying to model a problem to enable me to use Dijkstra's Shortest Path algorithm. Given are a set of vertices V, and a set of vertices X ⊂ V.

Between these vertices are given a set of edges where:

• edge(u,v) with u ∈ V \ X being weighted > 0
• edge (u,v) where u ∈ X being weighted = 0
• other edge combinations (i.e. u,v ∈ V and u,v ∈ V \ X) are allowed, but follow the same rules as above

At most two vertices ∈ X are allowed to be visited in the path.

How can this be modeled as a shortest path algorithm problem? I've seen solutions for at most one vertices ∈ X are allowed by splitting the graph into two copies but that doesn't quite hit my requirements.

Any help much appreciated!

Answer 1

You never say what the goal is. I suspect that you want to find the shortest a path from a given vertex $s$ to a given vertex $t$ that passes through at most two vertices in $X$. In this case you can assume w.l.o.g., that $s,t \not\in X$. Moreover, you can assume that the input graph is directed. If this is not the case, then you can preliminarily replace each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$.

Let $G=(V,E)$ be the input graph and let $F = \{ (u,v) \mid u \in X\}$ be the set of outgoing edges from some vertex in $X$. Make a new graph $H$ containing three copies $G_1, G_2, G_3$ of the graph $(V, E \setminus F)$. Then, augment the graph as follows:

• For each edge $(u,v) \in F$ add:
  • an edge (of weight $0$) between the copy of $u$ in $G_1$ and the copy of $v$ in $G_2$.
  • an edge (of weight $0$) between the copy of $u$ in $G_2$ and the copy of $v$ in $G_3$.
• Add a new vertex $t^*$ and the three edges (of weight 0) between each copy of $t$ in $G_1$, $G_2$, and $G_3$ and $t^*$.

You can now find a shortest path $P$ between the copy of $s$ in $G_1$ and $t^*$. The list of vertices traversed by $P$ (except for the final vertex $t^*$) will induce the sought shortest path on $G$.

Answer 2

I've seen solutions for at most one vertices ∈ X are allowed by splitting the graph into two copies but that doesn't quite hit my requirements.

Actually, it does. Just create two copies instead of one, linking the top-layer to the middle-layer, and the middle-layer to the bottom, via the nodes in X.

This works because the "copy the graph" trick is simply a way of encoding state by using graph nodes. In your case, each node has 3 copies, and which copy you're in tells you how many nodes in X you've traversed.