Solution: All Paths From Source to Target

Statement

You are given a directed acyclic graph (DAG) with $n$ nodes, labeled from $0$ to $n - 1$. The graph is represented as an adjacency list, where graph[i] is a list of all nodes to which node i has a directed edge to.

Your task is to find all possible paths from node $0$ (the source) to node $n - 1$ (the target) and return them as a list of paths. Each path should be represented as a list of node indexes.

Note: You may return the answer in any order.

Constraints:

• $2 \leq$ $n$ $\leq 15$

• $0 \leq$ graph[i][j] $<$ $n$

• All nodes in graph[i] are unique.

• The graph is guaranteed to be a DAG (no cycles).

• There are no self-loops (i.e., graph[i] does not contain i).

Solution

The essence of the solution lies in exploring all possible paths from the source node (node 0) to the target node (the last node) in a directed graph using depth-first search (DFS) combined with backtracking. The solution carefully tracks and records the current path whenever the destination is reached in a result list. A key insight here is that, because the graph is acyclic, there’s no risk of getting trapped in infinite loops — every path will either reach the target or terminate. Using this property, the solution starts at the source and recursively explores each neighbor, maintaining the current path throughout the traversal. After visiting a neighbor, it backtracks by removing the last node, ensuring that different paths don’t interfere with each other. This exploration guarantees that all valid paths are considered without redundancy. The core operation involves extending the current path by one neighbor, recursively exploring from there, and then backtracking to explore alternative routes. Once the recursion completes, the result list contains all possible paths from the source to the target.

Now, let’s look at the solution steps below:

1. We initialize an empty list result to store the final paths.

2. We determine the target as $\text{len(graph)} - 1$ (the last node index).

3. We start the DFS traversal by calling dfs(graph, 0, [0], result, target) — beginning from node 0 with an initial path containing just [0].

4. The definition DFS function is: dfs(graph, node, path, result, target), where:

   1. graph is the adjacency list of the graph.

   2. node is the current node we are visiting.

   3. path is the list of nodes visited so far in the current route.

   4. result is the list collecting all complete paths.

   5. target is the destination node (last node of the graph).

The function explores all possible paths from the current node to the target node.

5. Inside dfs, we first check if the current node is equal to the target:

   1. If it is, it means a complete path has been found that successfully reaches the target. We append this path to result list.

   2. Otherwise, for each neighbor of the current node in the graph:

      1. We append the neighbor to the path.

      2. We recursively call dfs to continue the exploration from this neighbor.

      3. After the recursive call, we backtrack by removing the neighbor from the path to return to the previous state and explore other branches.

6. Once DFS completes, result list is returned containing all the possible paths from source to target.

Let’s look at the following illustration to get a better understanding of the solution: