algoadvance

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 given as follows: graph[i] is a list of all nodes j for which the edge (i, j) exists.

Clarifying Questions

  1. Will there be any cycles in the graph?
    • No, the problem guarantees that the graph is a DAG (Directed Acyclic Graph).
  2. What should be the format of the output?
    • The output should be a list of lists, where each inner list represents a path from node 0 to node n-1.
  3. Can the graph be empty or have no edges?
    • The graph will have at least one edge since it’s a DAG from 0 to n-1.
  4. Any constraints on the graph size?
    • The typical constraint for such problems usually allows n up to 15 or 20, giving a feasible solution space for DFS.

Strategy

We need to find all paths from 0 to n-1. This can be efficiently done using Depth-First Search (DFS):

  1. Start from node 0.
  2. Continue exploring the nodes in a depth-first manner.
  3. Keep track of the current path.
  4. When you reach the target node n-1, save the current path.
  5. Backtrack and explore other paths.

This approach follows naturally due to the recursive nature of DFS. Given the DAG’s properties, the edges direct us without worrying about cycles.

Time Complexity

Code

def allPathsSourceTarget(graph):
        def dfs(node, path):
            if node == len(graph) - 1:
                result.append(path)
                return
            for next_node in graph[node]:
                dfs(next_node, path + [next_node])
        
        result = []
        dfs(0, [0])
        return result

# Example Usage
graph = [[1,2],[3],[3],[]]
print(allPathsSourceTarget(graph))
# Output: [[0, 1, 3], [0, 2, 3]]

Explanation

  1. Function Definition:
    • dfs(node, path) is a helper function that performs the DFS, starting from a given node and forming paths.
    • result list to store all paths from source to target.
  2. Base Case:
    • If the current node is the target node (len(graph) - 1), append the current path to results.
  3. Recursive Case:
    • Iterate over all possible next nodes from the graph adjacency list.
    • For each next node, call dfs recursively after appending the next node to the current path.
  4. Initial Call:
    • Start the DFS from node 0 with the initial path containing 0.

By following this strategy, we cover all paths by exploring them recursively in a depth-first manner.

Try our interview co-pilot at AlgoAdvance.com