Shortest path including all nodes in a subset

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

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

• If $p$ is a shortest path from $s$ to $t$ in $G$, then it will also appear in $G'$.

• For any vertex $v \in G'$, any path from $s$ to $v$ in $G'$ is a shortest path in $G$.

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

StackExchange Computer Science Q#134798, answer score: 3