shortest path from source to destination in directed graph with limitation

Question

Hello I'm taking the course Algorithm and I have this problem:

Let $G=(V,E)$ be a directed graph. Let $U \subset V$ a subset of $V$, and also let $s,t$ be two vertices such that $s \neq t \in V$ and $s, t \not\in U$.

I need to write an algorithm that find the shortest path from $s$ to $t$ which visits only two vertices in $U$. In this question I allowed to visit a vertex more than once (not have to be a simple path). In my book its says that I need to solve this with reduction. any suggestions?

I think I need to solve this with BFS...

Answer 1

For $k=0,1,2$ and $w\in V$, we compute $f(w,k)$, the length of the shortest path from $s$ to $w$ with $k$ visits to vertex in $U$. Ultimately, we find $f(t,2)$ and readily construct a corresponding path from $s$ to $t$: A path of length $f(w,k)$ from $s$ to $w$ with $k$ visits to $U$ is an edge $ve$ appended to a path from $s$ to $v$ of length $f(v,k')$ with $k'$ visits to $U$, where $k'=k$ or $=k-1$, depending on whether $w\in U$ or not.

1. Assign $f(w,k)\leftarrow \infty$ for all $w$ and $k$
2. Queue $(s,0,0)\Rightarrow Q$
3. If $Q$ is empty, terminate with failure (there is no suitable path)
4. Unqueue $Q\Rightarrow (v,k,d)$ and if $v\in U$ set $k\leftarrow k+1$.
5. If $k>2$ or $f(v,k)\ne \infty$, go back to step 3.
6. Set $f(v,k)\leftarrow d$. If $v=t$ and $k=2$, terminate with success (and compute the path as described above)
7. For each edge $vw$ beginning at $v$, queue $(w,k,d+1)\Rightarrow Q$
8. Go back to step 3