PROBLEM LINK:Author: Subham Das DIFFICULTY:MEDIUM PREREQUISITES:Directed Acyclic Graph, Topological Sort, Dynamic Programming PROBLEM:Given a DAG (directed acyclic graph) with N nodes and M edges, the problem requires one to find the number of different paths that exist from a given node P to another node Q. QUICK EXPLANATION:The first step is to toposort the given graph. If dp[u] be the number of paths from node u to node Q. Then dp[u] = summation of dp[v] for all v for each edge directed from u to v. We obtain dp[u] for each node u in the graph in reverse topological order. Then dp[P] is the required answer. EXPLANATION:Let $f(u)$ be the number of ways one can travel from node $u$ to node $Q$. Naturally, $f(P)$ is our required answer. $f(Q) = 1$ here, since there is just one way of travelling from $Q$ to $Q$, by not moving! We can observe that $f(u)$ depends on nothing other than the $f$ values of all the nodes it is possible to travel to from $u$. This makes sense because the number of ways we can travel from $u$ to $Q$ is the sum of all the ways we can travel from $v_1$, $v_2$, $v_3$... $v_n$ to $Q$ where $v_1$ to $v_n$ are all the nodes that can be directly travelled to from node $u$. Thus we have the formulation $$ f(u) = \sum f(v) \, for\, all\, v\ \mid \ an\, edge\ u\, \rightarrow v\ exists$$ Thus, our trivial function would look something like function f(u) if u equals Q return 1 sum = 0 for each edge u→v sum = sum + f(v) return sum The check statement " Since this problem exhibits both overlapping subproblems and optimal substructure, dynamic programming is applicable here. In order to evaluate $f(u)$ for each $u$ just once, we must make sure to evaluate $f(v)$ for all $v$ that can be visited from $u$ before evaluating $f(u)$. This condition is satisfied by reverse toposorted order of the nodes of the graph. Check out this Wiki article for more about topological sort. L = empty list D = array of indegrees for each node S = list of all nodes u with D[u] = 0 while S is not empty repeat remove a node u from S append u to the end of L for each edge u→v D[v] = D[v]  1 if D[v] equals 0 add v to S The next step is to use dynamic programming to calculate our $f$ values. We also need to make sure to store the values modulo 10^{9}+7. dp = array to store f values set dp[u] = 0 for each node u dp[Q] = 1 for each node u in revere order of L for each edge u→v dp[u] = dp[u] + dp[v] dp[u] = dp[u] % 1000000007 The last step is to print the value of Complexity of this approach is $O(N+M)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 14 Oct '16, 23:19
