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

  • $\begingroup$ 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"? $\endgroup$ – Hagen von Eitzen Oct 21 '18 at 11:07
  • $\begingroup$ exactly two.... $\endgroup$ – 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$
  8. Go back to step 3

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.