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 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!

$\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$ – user114966 Mar 8 at 23:54
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$.

$\endgroup$
1
  • $\begingroup$ Your assumptions are correct, apologies for not being completely clear! $\endgroup$ – f0body Mar 9 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.

$\endgroup$
1
  • $\begingroup$ Thank you, that makes a lot of sense. $\endgroup$ – f0body Mar 9 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.