Printing all the Paths from Source to Destination Node in Directed Acyclic Graph ( DAG )

In this article we will be solving 4 problems related to the path between source and destination node. These 4 problems are,

1. How many paths are there between u and v.
2. How many edges are there in the longest/shortest path.
3. How many nodes are there in the longest/shortest path.
4. Which node certainly appear in any path other than the source and destination nodes.

So let us understand our problem first by using an example, and solve the first problem with which we can solve all other.

In the given DAG we have 6 nodes numbered 1,2, ... ,6. And we are supposed to print all the paths from 1 (Source node) to node 6 (Destination node).

Which are,

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

So how should we do this. Well we can solve this problem using both DFS and BFS Algorithms. Here we will be using BFS.

• Now we know that to go from nodes 1 to 6 we need to traverse all the paths starting from 1 and select the path which takes us to 6.
• So let us start BFS with node 1. And take a look at the nodes where we reach from it
• Here from 1, we can reach 2 and 4 so two subpaths will be there.
• {1, 2} & {1, 4}
• Now we will explore both these subpaths and look at the last node in each whether it is 6 or not. If it is 6 then we have reached our destination so we can print this path. If not then we will explore from the last node.
• So exploring from {1, 2}, 2!=6 so we will start BFS at 2 which will take us to 3. And the subpath now became would be {1, 2, 3 }. 
• Now explore path {1,2,3 }, 3 != 6 so again start BFS at 3 which will take us to 6. And the subpath now became would be {1, 2, 3, 6}
• Now explore path { 1, 2, 3, 6 }, 6==6 so this is our one path.
• Red lines denote the path.

• Now let us explore from {1,4}, 4!=6 so start BFS at 4 which will take us to 5. And the path will become { 1, 4, 5 }.
• Now explore {1,4,5}, 5!=5 so start BFS from 5 which will take us to 2 and 3. Forming 2 new subpaths.
• {1, 4, 5, 2 } and { 1, 4, 5, 3 }
• Now let us explore {1, 4, 5, 2 }, 2!=6, start BFS from 2 which will take us to 3. And the subpath now will be { 1, 4, 5, 2, 3}.
• Now explore {1, 4, 5, 2, 3}, 3!=6 so start BFS from 3 which will take us to 6. And the subpath will be {1, 4, 5, 2, 3, 6}.
• Now explore {1, 4, 5, 2, 3, 6}, 6==6 so this is a valid path.
• Red lines denote the path.

• Now let us explore {1, 4, 5, 3 } 3!=6 so start BFS from 3 which will take us to 6. And subpath will be {1, 4, 5,  3, 6}.
• Now explore {1, 4, 5, 3, 6}, 6==6 so this is also a path.
• Red lines denote the path.

Implementation in C++

• The implementation is a simple BFS Algorithm in which instead of pushing a node to queue we will store a subpath.
• Like this, for path {1, 2, 3, 6 }. Initially push {1} to queue the start BFS from it.
• Then push subpath {1,2} & {1,4} to the queue.
• Then start to take subpath {1,2} and check whether the last node is equal to the destination node or not. If yes then that's the path push it to the result vector else start BFS from the last node and push that subpath to queue and so on until the queue gets empty.
• The complexity of this is Exponential as we need to traverse all the paths.

Now using this as a base solution, all the other questions can be answered like the number of paths from source to destination, max/min length path, etc. 

And that's all for this article, in next we will be looking into Dynamic Programming Approach to solve some of these problems. If there is any error or you have any doubt then feel free to comment.

Thank You for Reading.