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|$
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 &quot;useless&quot; 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 &quot;marking&quot; $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.)