Problem Description

You are given a directed acyclic graph (DAG) with n nodes labeled from 0 to n - 1. Your task is to find all possible paths that start from node 0 and end at node n - 1. You can return these paths in any order.

The graph is represented as an adjacency list where graph[i] contains a list of all nodes that can be reached directly from node i. In other words, if node j appears in graph[i], there is a directed edge from node i to node j.

For example:

• If [graph](/problems/graph_intro) = [[1,2],[3],[3],[]], this represents a graph with 4 nodes (0, 1, 2, 3)
• From node 0, you can go to nodes 1 and 2
• From node 1, you can go to node 3
• From node 2, you can go to node 3
• Node 3 has no outgoing edges

The paths from node 0 to node 3 would be: [[0,1,3], [0,2,3]]

Since the graph is a DAG, it has no cycles, which guarantees that all paths will eventually terminate and won't loop infinitely.

The solution uses a breadth-first search (BFS) approach with a queue to explore all possible paths. It starts with the path [0] and keeps extending each path by adding neighboring nodes until reaching the target node n - 1. When a path reaches the target node, it's added to the answer list. The algorithm continues until all possible paths have been explored.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly states we have a directed acyclic graph (DAG) with nodes and edges. The graph is represented as an adjacency list where graph[i] contains all nodes reachable from node i.

Is it a tree?

• No: While the graph is acyclic (being a DAG), it's not necessarily a tree. A tree has exactly one path between any two nodes, but in this problem, we're finding all possible paths from source to target, implying multiple paths can exist.

Is the problem related to directed acyclic graphs?

• Yes: The problem explicitly mentions we're dealing with a DAG and we need to find all paths from node 0 to node n-1.

Topological Sort

• While topological sort is often used with DAGs, this specific problem asks for all paths rather than an ordering of nodes. However, we need to continue evaluating...

Looking deeper at the problem requirements:

• We need to find all possible paths from source to target
• The graph has small constraints (typically n ≤ 15 for such problems)
• We need to explore every possible route exhaustively

Does the problem have small constraints?

• Yes: Problems asking for "all possible paths" typically have small constraints since the number of paths can grow exponentially.

DFS/backtracking

• Yes: This is the appropriate approach. We need to explore all paths from source to target, which requires systematically visiting each possible route and backtracking when we reach dead ends or the target.

Conclusion: The flowchart guides us to use DFS (Depth-First Search) with backtracking. This makes sense because:

1. We need to explore all complete paths from source to target
2. DFS naturally maintains the current path as it traverses
3. When we reach the target or a dead end, we backtrack to explore other branches
4. The small constraints make this exhaustive search feasible

Intuition

When we need to find all possible paths from a source to a target in a graph, we essentially need to explore every route systematically. Think of it like exploring all possible ways to get from your home to a destination in a city where streets only go one way (since it's a directed graph).

The key insight is that we need to keep track of our current path as we explore. Starting from node 0, we have multiple choices of where to go next. For each choice, we need to:

1. Add that node to our current path
2. Continue exploring from that new node
3. Remember to explore all other choices as well

This naturally leads to a traversal approach where we maintain the path we're currently exploring. When we reach the target node n-1, we've found a complete path and should save it. When we reach a dead end or finish exploring all neighbors of a node, we need to backtrack and try other options.

The solution uses BFS with a clever twist - instead of just storing nodes in the queue, it stores entire paths. Each element in the queue is a path (list of nodes) that we're currently exploring. For example:

• Start with path [0]
• If node 0 connects to nodes 1 and 2, we create two new paths: [0,1] and [0,2]
• We continue extending each path until it reaches the target

This approach works because:

• The graph is acyclic (DAG), so we won't get stuck in infinite loops
• By storing complete paths in the queue, we automatically keep track of the route we took
• When a path's last node is n-1, we know we've found a complete source-to-target path
• The BFS ensures we explore all possible paths systematically

While the provided solution uses BFS, DFS would work equally well here. The choice between BFS and DFS doesn't affect correctness since we need all paths anyway - both will explore the entire search space. The BFS approach with path tracking is just one clean way to implement this exhaustive search.

Learn more about Depth-First Search, Breadth-First Search, Graph and Backtracking patterns.

Solution Approach

The implementation uses a BFS approach with a queue to systematically explore all paths from source to target. Let's walk through the solution step by step:

Data Structures Used:

• deque: A double-ended queue to efficiently add and remove paths during BFS traversal
• ans: A list to store all valid paths from node 0 to node n-1

Algorithm Implementation:

1. Initialization:

   n = len([graph](/problems/graph_intro))
   q = deque([[0]])
   ans = []

   • Get the total number of nodes n from the graph
   • Initialize the queue with a single path [0] (starting from source node)
   • Create an empty answer list to store complete paths

2. BFS Traversal:

   while q:
       path = q.popleft()
       u = path[-1]

   • Process paths in the queue one by one
   • Extract the current path and get its last node u (the current position)

3. Check for Target:

   if u == n - 1:
       ans.append(path)
       continue

   • If the current node is the target (n-1), we've found a complete path
   • Add this path to our answer list
   • Continue to the next path in the queue (no need to explore further from the target)

4. Path Extension:

   for v in [graph](/problems/graph_intro)[u]:
       q.append(path + [v])

   • If we haven't reached the target, explore all neighbors of the current node
   • For each neighbor v, create a new path by appending v to the current path
   • Add this extended path to the queue for future exploration

Key Insights:

• By storing entire paths in the queue instead of just nodes, we automatically maintain the route taken to reach each node
• The path + [v] operation creates a new list, ensuring each path in the queue is independent
• Since the graph is a DAG, we don't need to track visited nodes - there are no cycles to worry about
• The algorithm naturally terminates when all paths have been explored (queue becomes empty)

Time Complexity: O(2^N × N) in the worst case, where N is the number of nodes. In the worst case, there could be 2^N paths (if the graph is fully connected), and each path can have up to N nodes.

Space Complexity: O(2^N × N) for storing all the paths in the queue and the answer list.

Example Walkthrough

Let's walk through a small example with graph = [[1,2],[3],[3],[]].

This represents a graph with 4 nodes (0→1, 0→2, 1→3, 2→3), and we need to find all paths from node 0 to node 3.

Initial State:

• Queue: [[0]]
• Answer: []

Iteration 1:

• Pop path [0] from queue
• Current node is 0 (last element of path)
• Node 0 is not the target (3), so explore neighbors
• Node 0 has neighbors [1, 2]
• Add new paths to queue: [0,1] and [0,2]
• Queue: [[0,1], [0,2]]

Iteration 2:

• Pop path [0,1] from queue
• Current node is 1
• Node 1 is not the target, so explore neighbors
• Node 1 has neighbor [3]
• Add new path to queue: [0,1,3]
• Queue: [[0,2], [0,1,3]]

Iteration 3:

• Pop path [0,2] from queue
• Current node is 2
• Node 2 is not the target, so explore neighbors
• Node 2 has neighbor [3]
• Add new path to queue: [0,2,3]
• Queue: [[0,1,3], [0,2,3]]

Iteration 4:

• Pop path [0,1,3] from queue
• Current node is 3
• Node 3 IS the target! Add path to answer
• Answer: [[0,1,3]]
• Queue: [[0,2,3]]

Iteration 5:

• Pop path [0,2,3] from queue
• Current node is 3
• Node 3 IS the target! Add path to answer
• Answer: [[0,1,3], [0,2,3]]
• Queue: []

Result: Queue is empty, algorithm terminates. We found all paths: [[0,1,3], [0,2,3]]

Solution Implementation

Time and Space Complexity

Time Complexity: O(2^N * N)

The algorithm performs a BFS traversal to find all paths from node 0 to node N-1 in a directed acyclic graph (DAG). In the worst case, we have a complete DAG where every node has edges to all subsequent nodes. This creates the maximum number of paths.

• The maximum number of paths from source to target in a DAG can be 2^(N-2) (considering nodes between source and target).
• For each path discovered, we create a new list by concatenating the current path with a new node, which takes O(N) time in the worst case (when the path length is N).
• Each node can be visited multiple times as part of different paths.
• Therefore, the total time complexity is O(2^N * N).

Space Complexity: O(2^N * N)

The space complexity consists of:

• Queue space: In the worst case, the queue can hold all possible partial paths simultaneously. The maximum number of paths that can exist is O(2^N), and each path can have up to N nodes, resulting in O(2^N * N) space.
• Answer list: The answer list stores all valid paths from source to target. In the worst case, there can be O(2^N) such paths, each of length up to N, requiring O(2^N * N) space.
• Path copies: When we do path + [v], we create a new list, but this is already accounted for in the queue space analysis.

The dominant factor is the storage of all paths, giving us a total space complexity of O(2^N * N).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Mutating the Same Path Object

One of the most common mistakes is reusing the same path list object when extending paths, which leads to all paths in the queue pointing to the same list.

Incorrect Implementation:

# WRONG: This modifies the same path object
for v in graph[u]:
    path.append(v)  # Mutates the original path
    q.append(path)  # All queue entries point to the same list
    path.pop()  # Trying to backtrack, but damage is already done

Why it fails: When you append the same list object to the queue multiple times, all references point to the same list in memory. Any modification affects all "copies" in the queue.

Correct Solution:

# RIGHT: Create a new path for each neighbor
for v in graph[u]:
    q.append(path + [v])  # Creates a new list object

2. Using DFS with Incorrect Backtracking

When implementing this with DFS instead of BFS, forgetting to properly backtrack the path state is a common error.

Incorrect DFS Implementation:

def dfs(node, path):
    if node == n - 1:
        ans.append(path)  # WRONG: Appending reference to mutable path
        return
  
    for neighbor in graph[node]:
        path.append(neighbor)
        dfs(neighbor, path)
        # Forgot to backtrack: path.pop()

Correct DFS Solution:

def dfs(node, path):
    if node == n - 1:
        ans.append(path[:])  # Create a copy of the path
        return
  
    for neighbor in graph[node]:
        path.append(neighbor)
        dfs(neighbor, path)
        path.pop()  # Proper backtracking

3. Memory Inefficiency with Large Graphs

Storing complete paths in the queue can consume excessive memory for graphs with many paths.

Problem Scenario:

• In a densely connected DAG, the number of paths can grow exponentially
• Each path is stored as a separate list in the queue
• This can lead to memory overflow for large graphs

Optimized Alternative Using DFS:

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def dfs(node, path):
            # Process one path at a time, reducing memory footprint
            if node == len(graph) - 1:
                result.append(path)
                return
          
            for neighbor in graph[node]:
                dfs(neighbor, path + [neighbor])
      
        result = []
        dfs(0, [0])
        return result

This DFS approach uses the call stack instead of explicitly storing all partial paths, which can be more memory-efficient in practice.