[Solved]: Shortest path that visits maximum number of strongly connected components

Problem Detail: 

Consider a directed graph. I need to find a path that visits maximum number of strongly connected components in that graph. If there are several such paths the desired path is the path that visits minimum number of nodes (shortest path).

I have created a DAG from the directed graph and performed a topological sort on it. Now I can easily find paths that passes maximum number of components by traversing the DAG, but I have problem finding the shortest one of them. Of course you can brute-force over all of these paths and find the shortest one of them but this is not acceptable because my graph has 1000 nodes.

Asked By : sudomakeinstall2

Answered By : David Richerby

For ease of writing, I'm going to say "component" instead of "strongly connected component." This should cause no confusion, since it's the only kind of component we're interested in.

Let $G$ be your directed graph. Let $H$ be the DAG made by contracting every component of $G$ to a single vertex. That is, the vertices of $H$ are the components of $G$ and there's an edge from $x$ to $y$ in $H$ if, and only if, there's an edge in $G$ from the component corresponding to $x$ from the one corresponding to $y$. Write $h(C)$ for the vertex in $H$ that corresponds to the component $C$ in $G$.

Observe that any path in $G$ that visits the maximum possible number of components must correspond to a maximum-length path in $H$, which must run from some source to some sink. So, we need to find the longest paths in $H$. We can't just produce a list of them because there might be exponentially many. So, instead, we assign a label $\ell(x)$ to every $x\in V(H)$ using the following procedure.

• Topologically sort the vertices.
• Set $\ell(x) = 0$ for each sink $x$.
• Working back from the leaves in the topological ordering, set $\ell(x) = 1 + \max\,\{\ell(y_1), \dots, \ell(y_k)\}$ for each vertex $x$ with out-neighbours $y_1, \dots, y_k$.

Note that the topological ordering guarantees that we've already computed $\ell(y_i)$ for each out-neighbour $y_i$. When the labelling is computed, it has the property that, for every vertex $x\in H$, $\ell(x)$ is the length of the longest path from $x$ to a sink in $H$.

Now, produce a graph $H'$ from $H$ as follows.

• Delete every edge $(x,y)$ such that $\ell(x)\neq\ell(y)+1$.
• Let $m = \max\,\{\ell(x)\mid x\text{ is a source in }H\}$ (this is the length of the longest path in $H$).
• Iteratively delete every source $y$ with $\ell(y)<m$.

$H'$ contains exactly the vertices and edges of $H$ that appear in longest paths in $H$ (put another way, $H'$ is the union of all longest paths in $H$). In particular, every path from a source to a sink in $H'$ has length exactly $m$, which is the greatest length of any path in $H$.

Now, produce a graph $G'$ from $G$ as follows.

• Delete from $G$ any component $C$ such that $h(C)\notin H'$.
• Delete from $G$ any edge from component $C_1$ to component $C_2$ if there is no edge $(h(C_1),h(C_2))$ in $H'$.

Finally, let $S\subseteq V(G')$ be the set of all vertices whose components are sources in $H'$ and let $T\subseteq V(G')$ be the vertices in components that are sinks in $H'$. The $S$ $T$ paths in $G'$ are exactly the paths in $G$ that visit the maximum possible number of components. Use your favourite shortest path algorithm to find a shortest one.

_{Thanks to Bakuriu for suggesting topological sort instead of my ad-hoc algorithm.}

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49481