This series of articles covers a set of popular computer science problems.
The problem:
Given a directed acyclic graph of n nodes labeled from 0 to n-1, find all possible paths from node 0 to node n-1 and return them in any order.
The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (meaning, there is a directed edge from node i to node graph[i][j] for all j).
The solution:
def allPathsSourceTarget(graph):
paths = []
get_paths(graph, 0, [], paths)
return paths
def get_paths(graph, node, current, paths):
if node == len(graph) - 1:
paths.append(current + [node])
for adj in graph[node]:
get_paths(graph, adj, current + [node], paths)
Your email address will not be published. Required fields are marked *
