Shortest path including all nodes in a subset

Question

Given a directed graph $G=(V, E)$, two nodes $s, t \in V$ and a subset of nodes $U \subseteq V$.

Provide an algorithm that determines if there is a shortest path from $s$ to $t$ that passes via all nodes in $U$.

I came across a solution that starts with the following steps

• Run BFS on G, notate $d_s(v) \quad \forall v \in V$
• Calculate $G^T$ (transposed graph)
• Run BFS on $G^T$, notate $d_t(v) \quad \forall v \in V$
• Build $G^{'} = (V, E^{'})$ where $E^{'} = \{(u,v)\in E | d_s(u) + 1 + d_t(v) = d_s(t)\}$

I don't quite understand the intuition for this specific build. It resembles the building of G scc with DFS which doesn't contribute much to my understanding.

Why would I want to build the graph this way and not use the shortest-path-tree I got from the first BFS execution?

EDIT: continued algorithm steps are:

• Run topological sort on $G^{'}$, notate the result with $a_1, a_2,...,a_k$.
• Initialize field $c(v)=0 \quad \forall v \in V$
• Initialize starting node $v \leftarrow t$
• For all v in the reverse topological order do: (until arriving at s)
  {
  $\forall (x, v) \in E^{'}$
  {
  if $v \in U, c(x) \leftarrow max\{c(x), c(v)+1\}$
  else $c(x) \leftarrow max \{c(x), c(v)\}$
  }
  }
• Return $c(s) == |U|$

Answer 1

$d_{t}(s)$ denote the shortest path length from $s$ to $v$ in $G$.

$d_{t}(v)$ denote the shortest path length from $v$ to $t$ in $G$.

Using this, the algorithm is constructing $G'$ which consists of exactly those edges of $G$ that appear in some shortest path from $s$ to $t$.

The construction of $G'$ uses the following property of shortest paths.

Property 1: A path $p = (u_{1},u_2,\dotsc,u_{\ell})$ is shortest path from $u_{1}$ to $u_{\ell}$ if and only if $(u_{1},u_{2},\dotsc, u_{i})$ is a shortest path from $u_{1}$ to $u_{i}$ and $(u_{i},\dotsc,u_{\ell})$ is a shortest path from $u_{i}$ to $u_{\ell}$ for every $i \in \{1,\dotsc,\ell\}$.

Using Property 1, you can further prove the following properties of graph $G'$:

1. If $p$ is a shortest path from $s$ to $t$ in $G$, then it will also appear in $G'$.
2. For any vertex $v \in G'$, any path from $s$ to $v$ in $G'$ is a shortest path in $G$.
3. $G'$ is acyclic

Therefore, the algorithm simply checks in $G'$ if there is any path from $s$ to $t$ that contains all vertices in $U$. If it does contains such a path (i.e., $c(v) = |U|$), then that path is a shortest path by the definition of $G'$. And, if there is no such path, then there is no such path in $G$ as well.

Answer 2

The purpose of the BFS in the transposed graph is to eliminate edges that are part of shortest paths to some vertex, but not to $t$. These "useless" edges could otherwise lead to false positives in the traceback phase that builds $c(\cdot)$.

Consider the digraph with $E=\{st,su\}$ and $U=\{u\}$. The unique shortest path is the single edge $st$, so the answer is NO, but unless you know that the $su$ edge should be ignored (by making use of the transposed graph), the traceback phase will process it (on either its first or second iteration) and assign $c(s)=1$, resulting in YES being reported.

(Alternatively, you could augment the traceback phase by "marking" $t$ and any edge into a marked vertex, and considering only values of $c(\cdot)$ for marked vertices. This is fairly similar to just performing a backwards BFS from $t$, and probably a little more efficient in practice.)