# shortest path from source to destination in directed graph with limitation

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

• What advantage should vertex repetition give you? Do we have to visit two $U$-vertices (or alternatively one vertex twice), or does "only two" mean what I'd understand it to mean, namely "zero, one, or two"? – Hagen von Eitzen Oct 21 '18 at 11:07
• exactly two.... – joe Oct 21 '18 at 11:09

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