# 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|$$
• @InuyashaYagami added the full solution. Jan 26 at 8:31

## 2 Answers

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

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