I am trying to find all possible paths from a given source to destination. I created a directed acyclic graph using the NetworkX library of python. Finding all possible paths is a time exponential problem. I have seen a lot of suggestions about using dynamic programming to improve timing but I could not find any solution that how can I use dynamic programming in this case. Here are the three different approaches I am using for finding all possible paths between two nodes. First approach,
def find_all_paths(graph, start, end, path=): path = path + [start] if start == end: return [path] paths =  for node in graph[start]: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths
def all_simple_paths(G, source, target, cutoff=None): if source not in G: raise nx.NetworkXError('source node %s not in graph'%source) if target not in G: raise nx.NetworkXError('target node %s not in graph'%target) if cutoff is None: cutoff = len(G)-1 if G.is_multigraph(): raise NetworkXError("astar_path() not implemented for Multi(Di)Graphs") else: return _all_simple_paths_graph(G, source, target, cutoff=cutoff) def _all_simple_paths_graph(G, source, target, cutoff=None): if cutoff < 1: return visited = [source] stack = [iter(G[source])] while stack: children = stack[-1] child = next(children, None) if child is None: stack.pop() visited.pop() elif len(visited) < cutoff: if child == target: yield visited + [target] elif child not in visited: visited.append(child) stack.append(iter(G[child])) else: #len(visited) == cutoff: if child == target or target in children: yield visited + [target] stack.pop() visited.pop()
def printAllPathsUtil(G, u, d, visited, path): sid = G.node[u]['nodeID'] did = G.node[d]['nodeID'] # Mark the current node as visited and store in path visited[sid]= True path.append(u) # If current vertex is same as destination, then print # current path if u == d: global pathlist pathlist.append(path) else: # If current vertex is not destination #Recur for all the vertices adjacent to this vertex for i in G.neighbors(u): j = G.node[i]['nodeID'] if visited[j]==False: printAllPathsUtil(G, i, d, visited, path) # Remove current vertex from path and mark it as unvisited path.pop() visited[sid]= False def printAllPaths(G,s, d): # Mark all the vertices as not visited visited =[False]*G.number_of_nodes() # Create an array to store paths path =  global pathlist # Call the recursive helper function to print all paths printAllPathsUtil(G, s, d,visited, path) return pathlist
Any help in this regard is appreciated.