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

Here is a short python example of a modified DFS to achieve this:

data = {1 : [2,3],   # Directed acyclic graph adjacency list
        2 : [3],
        3 : [4,5],
        4 : [5]}

def dfs(data, path, paths = []):   
    datum = path[-1]              
    if datum in data:
        for val in data[datum]:
            new_path = path + [val]
            paths = dfs(data, new_path, paths)
    else:
        paths += [path]
    return paths

Input:

print dfs(data = data, path = [1], paths = []) # adjacency list; a list containing the node to start from; and initialize an empty list for all possible paths

Output:

[[1, 2, 3, 4, 5], 
[1, 2, 3, 5], 
[1, 3, 4, 5], 
[1, 3, 5]]

Answer 2

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