PROBLEM LINK:
Author: Subham Das
Tester: Soumik Sarkar
Editorialist: Soumik Sarkar
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
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 “u equals Q” is our base case. When we reach our destination, we return 1 as mentioned above.
This approach however, is too slow to be of use. Each function call branches out into further calls, and that branches into further calls, until each and every path is explored once. The problem with this approach is that we calculate the same f(u) again and again each time the function is called with argument u.
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.
Kahn’s algorithm for toposorting a DAG is provided below
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 109+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 dp[P].
Complexity of this approach is O(N+M).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.