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!