### Graph Theory Problem Solving - Session 13 ( 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:**

**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**_{1}) + path(a_{2}) + path (a_{3}) + ... + path(a_{k})

- where a
_{1}, a_{2}, a_{3}, ... , 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.

**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 )**

That's all for this article, in the next session we will be discussing

If you have some

Thank You

**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 CODELABS3277**
## Comments

## Post a Comment