Question

Given a directed acyclic graph G= (V,E), vertex s∈V, design a dynamic programming algorithm to compute the number of distinct paths from s to v for any v∈V.

1. Define subproblems

2. Write recursion

3. Give the pseudo-code

4. Analyze the running time.

Answer 1

1. Subproblem will be based on fact that number of distinct paths from s to v will be equal to sum of number of distinct path from s to u for every neighbor u having edge incident on v.

2. Let N(v) denotes the number of distinct paths from s to v then we can recursively solve this problem with equation

3. An interesting property of directed acyclic graph (DAG) is that if we perform depth first search(DFS) on it and then sort the vertices in descending order of finish time, then we will get topological order such that for any edge (u,v) in edge set E, vertex u always comes before v in topological order.

Once topological order is in hand, we can calculate value of N(u) before N(v) if edge (u,v) exist so that we can finally calculate array N for every vertices in V.

Find_Distinct_Paths(G=(V,E) , s)

1. Compute DFS on G starting from vertex s.

2. Sort all the vertices into array A based on finish time to get vertices in V arranged in topological order in array A.

3. Set N(s) = 1 and N(v) = 0 //initialization step

4. For k = 2 to |V| //starting from index 2 because A[1] is vertex s

5...........u = A[k]

6...........for all vertex v outgoing from u: //outgoing neighbours of u

7......................N(v) = N(v) + N(u) //recursive step

8. Return

Above algorithm returns array N where N(v) is number of distinct path from s to v.

4. Performing DFS algorithm on graph G and arranging them in topological order takes O(|V|+|E|) time. There after again processing over each vertices and edges to compute N(v) for every v in V takes O(|V|+|E|) time leading to total time complexity of O(|V|+|E|).

Please comment for any clarification