Acyclic Graph Problem Solving using Dynamic Programming

In this article, we will be solving some of the Classic Problem from the Acyclic Graph which requires the Dynamic Programming Approach. The problems are,

• How many different paths are there from source (u) node to the destination node (v)?
• What is the shortest/ longest path from the source (u) node to the destination (v) node?
• What is the minimum/maximum number of edges in a path from the source (u) node to the destination (v) node?
• Which nodes certainly appear in any path from the source (u) node to the destination (v) node?

Prerequisite:

• Topological Sorting

For all the problem input will be an Acyclic Graph. In our case,

• First-line will take input n, m, where n-number of nodes, m-number of edges.
• The next m lines will take input u,v i.e edge u->v ( Directed Edge ).
• The next line will take the source and destination as input.

The naive approach for solving these problems is based on finding all the paths from u to v.

Counting the number of paths from the source (u) node to the destination node (v)?

So let us understand our problem first by using an example, 

In the given DAG we have 6 nodes numbered 1,2, ... ,6. And we are supposed to count the number of paths from 1 (Source node) to node 6 (Destination node). On listing the path we get these 3 paths,

• 1 -> 2 -> 3 -> 6
• 1 -> 4 -> 5 -> 3 -> 6
• 1 -> 4 -> 5 -> 2 -> 3 -> 6

Okay, so that we get by listing, but we don't want this as it's running time is Exponential. So let us use Dynamic Programming here,

• Let path(x) denote the number of paths from node 1 to node x. As a base case, path(1)=1. Then to calculate values of the path(x), we can use the following recursion

path(x) = path(a₁) + path(a₂) + path (a₃) + ... + path(a_k)

• where a₁, a₂, a₃, ... , a_k are the nodes from which there is an edge to x.
• Since the graph is acyclic, the value of path(x) can be calculated in order of a topological sort. A topological sort for the above graph is as follows,

{ 1, 4, 5, 2, 3, 6 }

• Hence the number of paths are as follows

The above path count is calculated as

• We have a path(1)=1 as the base case.
• Now we start traversing this in the topological order, so we go to 4, and we can reach 4 from just one node i.e. 1. And hence path(4) = path(1) = 1
• Similarly, path(5) = path(4) = 1
• Similarly, path(2) = path(1) + path(5) = 1 + 1 = 2. As we can reach 2 from 1 and 5.
• Similarly, path(3) = path(2) + path(5) = 2 + 1 = 3,
• And at last path(6) = path(3) = 3.

Implementation: 

• Store the graph in Adjacency List
• Find topological order
• Then iterate over the Topological order according to the above Rule
• Our code checks for a cycle and if it is not present then generate the TopSort and process further.

	#include<bits/stdc++.h>
	using namespace std; // Don't use in Serious Projects
	vector<int> order; // stores the reverse order of topsort.
	int color[100001]={0}; // initially
	//all nodes are unprocessed.
	bool pres[100001]={false};
	bool cycle=false;
	// function to check for cycle
	void dfs(vector<int> adj[], int s){
	color[s]=1; // Processing node - gray
	for(auto u: adj[s]){
	if(color[u]==1) cycle=true;
	if(color[u]==0) dfs(adj,u);
	}
	color[s]=2; // Processed node - black
	}
	// function to get the reverse topsort
	void topsort(bool visited[], vector<int> adj[], int s){
	for(auto u: adj[s]){
	if(visited[u]) continue;
	visited[u]=true;
	topsort(visited, adj, u);
	}
	if(!pres[s]) order.push_back(s);
	pres[s]=true;
	}
	int main(){
	int n,m; cin>>n>>m;
	vector<int> adj[n+1], reachedby[n+1];
	for(int i=0; i<m; i++){
	int u,v; cin>>u>>v;
	adj[u].push_back(v);
	reachedby[v].push_back(u);
	}
	bool visited[n+1];
	for(int i=1; i<=n; i++) if(color[i]==0) dfs(adj,i);
	memset(visited,false,sizeof(visited));
	if(!cycle){
	for(int i=n; i>=1; i--){
	if(!visited[i]){
	visited[i]=true;
	topsort(visited,adj,i);
	}
	}
	}
	if(cycle) puts("Cycle is Present.");
	else {
	reverse(order.begin(), order.end());
	// Source and destination nodes
	int u,v; cin>>u>>v;
	vector<int> dp(n+1,0);
	dp[u]=1; // Base case
	for(int i=0; i<n; i++){
	if(u==order[i]){
	for(int j=i+1; j<=n; j++){
	for(auto a: reachedby[order[j]]){
	dp[order[j]]+=dp[a];
	}
	}
	break;
	}
	}
	cout<<"Number of paths from: "<<u<<" to "<<v<<": "<<dp[v]<<"\n";
	}
	return 0;
	}

view raw 0CountingNumberOfPathsInDAGfromUV.cpp hosted with ❤ by GitHub

	6 7
	1 2
	1 4
	4 5
	5 2
	2 3
	3 6
	5 3
	1 6

view raw 1input.txt hosted with ❤ by GitHub

Number of paths from: 1 to 6: 3

view raw 1output.txt hosted with ❤ by GitHub

	6 7
	1 2
	1 4
	4 5
	5 2
	2 3
	3 6
	5 3
	2 6

view raw 2input.txt hosted with ❤ by GitHub

Number of paths from: 2 to 6: 1

view raw 2output.txt hosted with ❤ by GitHub

Summary

Here, we have found the number of paths from source to destination node. This same can be tweaked further to solve the rest of the three problems. Which you should implement now and if you have any issue then ask in the comment.

Practice Problems ( Random )

1. Ice Skating ( 217A )
2. Queue At the School ( 266B )
3. Soldier and Cards ( 546C )
4. New Year Permutation ( 500B )
5. Fox and two Dots? ( 510B )
6. Cycle in a Graph ( 263D )

That's all for this article, in the next session we will be discussing Successor Path, Cycle Detection using Floyd's Algorithm and Problems related to it and for now practice problems. ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA