algorithm - Enumerating all paths in a directed acyclic graph

Question

Is there any standard algorithm that finds all possible paths in a directed a-cyclic graph. If not, how can i make changes in BFS/Dijkstra/any other algorithm to enumerate all paths in a DAG

Answer 1

Finding all the possible paths in any graph in Exponential. It can be solved by using Backtracking. For DAG's we can do it using Depth first search(DFS). In DFS code, Start at any node, Go to the extreme dead end path and note down all the nodes visited in that path using some array or list. As soon as you find a dead end print the array containing the visited nodes and pop the last stored node and start in the other path of the (n-1)th node. If all the paths of the (n-1)th node are exhausted pop that node from list and start at (n-2)node. Do this untill you reach all the dead ends and reach the first node. All the Printed paths are the Paths in the given DAG.

You can check the code http://pastebin.com/p6ciRJCU