We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

All Paths From Source to Target

Difficulty: Medium

Problem Description

Given a directed acyclic graph (DAG) 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 represented such that graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to graph[i][j]).

Key Insights

  • The problem involves finding all paths in a directed acyclic graph (DAG) from a source node (0) to a target node (n-1).
  • Since the graph is a DAG, there are no cycles, which simplifies the pathfinding process.
  • A backtracking or depth-first search (DFS) approach is suitable for exploring all possible paths.
  • Keeping track of visited nodes and the current path is essential to avoid revisiting nodes and to build valid paths.

Space and Time Complexity

Time Complexity: O(2^N) in the worst case, where N is the number of nodes, due to the exponential number of paths in a DAG.
Space Complexity: O(N) for the recursion stack and storing paths.

Solution

To solve the problem, we can use a Depth-First Search (DFS) algorithm. The idea is to start from the source node (0) and recursively explore all possible paths to the target node (n - 1). We maintain a list to keep track of the current path and add it to the result list when we reach the target node. The algorithm uses a backtracking approach to explore different paths by removing the last visited node from the current path once all its neighbors are explored.

Code Solutions

def allPathsSourceTarget(graph):
    def dfs(node, path):
        # If we reached the target node, add the current path to the result
        if node == len(graph) - 1:
            result.append(path)
            return
        
        # Explore each neighbor of the current node
        for neighbor in graph[node]:
            dfs(neighbor, path + [neighbor])
    
    result = []
    dfs(0, [0])  # Start DFS from node 0 with the initial path [0]
    return result
← Back to All Questions