Code Implementation

class Solution:
    def allPathsSourceTarget(self, graph):
        res = []
        path = [0]
        target = len(graph) - 1

        def dfs(node):
            if node == target:
                res.append(list(path))
                return
            for nei in graph[node]:
                path.append(nei)
                dfs(nei)
                path.pop()
        dfs(0)
        return res
      

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;
        vector<int> path = {0};
        int target = graph.size() - 1;
        dfs(graph, 0, target, path, res);
        return res;
    }
    void dfs(vector<vector<int>>& graph, int node, int target, vector<int>& path, vector<vector<int>>& res) {
        if (node == target) {
            res.push_back(path);
            return;
        }
        for (int nei : graph[node]) {
            path.push_back(nei);
            dfs(graph, nei, target, path, res);
            path.pop_back();
        }
    }
};
      

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(graph, 0, path, res);
        return res;
    }

    private void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> res) {
        if (node == graph.length - 1) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int nei : graph[node]) {
            path.add(nei);
            dfs(graph, nei, path, res);
            path.remove(path.size() - 1);
        }
    }
}
      

var allPathsSourceTarget = function(graph) {
    const res = [];
    const path = [0];
    const target = graph.length - 1;

    function dfs(node) {
        if (node === target) {
            res.push([...path]);
            return;
        }
        for (let nei of graph[node]) {
            path.push(nei);
            dfs(nei);
            path.pop();
        }
    }
    dfs(0);
    return res;
};
      

Problem Description

Given a directed acyclic graph (DAG) represented as an adjacency list, your task is to find all possible paths from the source node (node 0) to the target node (node n - 1), where n is the number of nodes in the graph.

The input is a list of lists, where graph[i] contains all nodes that node i points to directly. You must return a list of all valid paths from the source to the target, with each path represented as a list of node indices.

Key constraints:

• All paths must start at node 0 and end at node n - 1.
• You may not revisit nodes in a path (since the graph is acyclic).
• Return all possible valid paths (not just one).

Thought Process

The challenge is to systematically explore all possible ways to get from the source to the target in a directed acyclic graph. At first glance, it might seem like we could simply "walk" from node 0 to node n - 1, but since there may be multiple choices at each node, we need to consider every combination.

A brute-force approach would mean trying every possible route, backtracking when we reach a dead end or reach the target. This naturally leads us to consider Depth-First Search (DFS), where we "dive" down each possible path, and back up to try alternatives.

Since the graph is acyclic, we don't need to worry about cycles or infinite loops. Also, since we want all paths, we can't stop at the first solution; we must collect every valid route.

Solution Approach

We can solve this problem using a recursive DFS (Depth-First Search) approach. Here’s how:

1. Start at node 0: Begin with a path list containing just the source node.
2. Recursive exploration: For each node, recursively explore all its neighbors by adding them to the current path and continuing the search.
3. Base case: If we reach the target node (n - 1), we add a copy of the current path to our results.
4. Backtracking: After exploring each neighbor, remove it from the path (backtrack) to try other possibilities.
5. Result collection: Collect all paths that reach the target node.

Why use DFS? DFS is ideal because it naturally follows each path to the end before trying alternatives. Since the graph has no cycles, we don’t need to keep a visited set for this problem.

Example Walkthrough

Let’s use the sample input graph = [[1,2], [3], [3], []]. This means:

• Node 0 points to nodes 1 and 2
• Node 1 points to node 3
• Node 2 points to node 3
• Node 3 is the target (no outgoing edges)

Here’s how the DFS would unfold:

1. Start at 0: path = [0]
2. Go to 1: path = [0,1]
3. Go to 3: path = [0,1,3] (reached target, add to results)
4. Backtrack to 0, try 2: path = [0,2]
5. Go to 3: path = [0,2,3] (reached target, add to results)

Time and Space Complexity

Brute-force approach: In the worst case, where every node connects to every other node, the number of possible paths from source to target could be exponential in the number of nodes, i.e., up to O(2ⁿ) for n nodes.

Optimized approach (DFS):

• Time Complexity: O(2ⁿ * n) in the worst case. Each path can be up to length n, and there can be up to O(2ⁿ) paths.
• Space Complexity: O(2ⁿ * n) to store all possible paths, plus O(n) for the recursion stack.

Summary

To solve "All Paths From Source to Target," we use depth-first search to explore every possible path from the source to the target in the directed acyclic graph. DFS is well-suited for this task because it allows us to build up each path step by step and backtrack efficiently. The key insight is that, since the graph is acyclic, we don’t need to worry about cycles, and we can safely use recursion and backtracking to enumerate all valid paths. The solution is elegant in its simplicity and leverages the natural structure of DFS for pathfinding in graphs.