Shortest path including all nodes in a subset
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.)