4
$\begingroup$

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|$
$\endgroup$
1
  • $\begingroup$ @InuyashaYagami added the full solution. $\endgroup$ Jan 26 at 8:31
3
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.