0
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Mar 8, 2021 at 23:54

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your assumptions are correct, apologies for not being completely clear! $\endgroup$ Commented Mar 9, 2021 at 11:20
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, that makes a lot of sense. $\endgroup$ Commented Mar 9, 2021 at 11:18

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.