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

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 XV.

Between these vertices are given a set of edges where:

• edge(u,v) with uV \ X being weighted > 0
• edge (u,v) where uX being weighted = 0
• other edge combinations (i.e. u,vV and u,vV \ 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!

• What do you mean by "splitting the graph into two copies"? If this is what I think, its modification from "at most one vertex" to "at most two vertices" is trivial.
– user114966
Mar 8, 2021 at 23:54

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$$.

• Your assumptions are correct, apologies for not being completely clear! Mar 9, 2021 at 11:20

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.

• Thank you, that makes a lot of sense. Mar 9, 2021 at 11:18