797. All Paths From Source to Target

MediumDepth-First SearchBreadth-First SearchGraphBacktracking

Problem Description

The problem presents us with a directed acyclic graph (DAG) that consists of n nodes labeled from 0 to n - 1. The goal is to find all the distinct paths that lead from node 0 to node n - 1 and return the collection of these paths. The definition of the graph is such that for every node i, there is a list of nodes, graph[i], that can be reached directly from node i through a directed edge. In simple terms, if we can travel from node i to node j, then j would be included in the list that corresponds with graph[i]. Since the graph is a DAG, there are no cycles, meaning we won't revisit any node once visited on the same path, which simplifies the traversal process.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here's a step-by-step guide to determine the appropriate algorithm for LeetCode Problem 797: All Paths From Source to Target.

Is it a graph?

Yes: The problem explicitly involves navigating from a source node to a target node within a directed acyclic graph (DAG).

Is it a tree?

No: Although a tree is a type of graph, the problem's graph can contain forks (multiple choices from a single node), which isn't characteristic of trees.

Is the problem related to directed acyclic graphs (DAGs)?

Yes: The problem's graph is specifically described as a DAG.

Does the problem involve finding topological sorts?

No: We need to find all possible paths from source to target, not sort the nodes.

Is the problem related to shortest paths?

No: The requirement is to list all paths, not find the shortest.

Conclusion: Based on the flowchart, the problem suits the Depth-First Search (DFS) strategy because it involves exploring all paths in a graph structure which is specifically a DAG. DFS is particularly handy to track paths and backtrack when necessary (e.g., when you hit a dead end or reach the target), which effectively gathers all possible paths in the structured order needed.

Intuition

The key insight to solving this problem lies in understanding that since the graph is acyclic, we can explore it without worrying about getting stuck in a cycle. This allows us to employ depth-first search (DFS) or breadth-first search (BFS) strategies to traverse the graph from the start node (node 0) to the end node (node n - 1).

The provided solution uses BFS. The idea behind BFS is to explore the graph level by level, starting from the source node. Here, we initiate a queue (FIFO structure) to keep track of the paths as we discover them. We start by enqueuing the path containing just the source node [0].

For each path taken out of the queue, we look at the last node in the path (current node) and explore all the nodes connected to it as follows:

If the current node is our destination node (n - 1), we've found a complete path from source to destination, so we add it to our list of answers.
If it's not the destination, we append each neighbor of the current node to a new path and enqueue these new paths back into the queue to be explored later.

This process is repeated until there are no more paths in the queue, meaning we've explored all possible paths from the source to the destination. At the end of this process, the ans list contains all unique paths from node 0 to node n - 1, and we return it as the final result.

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

Solution Approach

The given solution employs BFS, a common algorithm used for graph traversal that explores neighbors of a node before moving on to the next level of neighbors. In this approach, a queue is vital, which in Python, can be efficiently implemented using the collections.deque allowing for fast appends and pops from both ends.

Here are the steps involved in the solution:

Initialize a queue q and push the path containing the start node [0] onto it.
Create a list ans to store the answer - all the paths from source to target.
While the queue q is not empty, repeat the following steps:
- Pop the first path from the left of the queue (using popleft()).
- Get the last node in the path (current node u).
- If u is equal to n - 1 (target node), then the path is a complete path from source to target. It's then added to the ans list.
- If u is not the target, for each neighbor v of u, create a new path that extends the current path by v and enqueue it back into the queue q for further exploration.
Continue this process until the queue is empty, which means all paths have been explored.
Return the ans list containing all the successful paths.

By using BFS and a queue, we ensure that each node in a path is only visited once and that all paths are explored systematically. It guarantees that when we reach node n - 1, the path we have constructed is a valid path from node 0 to node n - 1, and since there are no cycles in a DAG, each path we discover is guaranteed to be a simple path (no repeated nodes).

The use of a path list that is extended and queued at each step avoids mutating any shared state, ensuring that paths discovered in parallel do not interfere with each other. Each discovered path is independent and can be appended to the ans list without any additional checks for validity, since the BFS approach inherently takes care of ensuring that a path is not revisited.

In summary, the BFS-based solution is an efficient way to traverse the graph and find all paths from the source to the destination in a DAG.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Given a directed acyclic graph (DAG) defined as graph = [[1,2], [3], [3], []], let's illustrate how the provided BFS solution approach would find all distinct paths from node 0 to node 3.

Start by initializing the queue q with the path containing just the start node [0]. Therefore, q = [[0]].
The list ans to store the answers is initialized as empty: ans = [].

Now, we start the BFS process:

q is [0]. We take out [0] for processing (dequeue operation).
The last node in the path [0] is 0. Since 0 is not the target node (3), we look at its neighbors.
According to graph[0], the neighbors are [1, 2]. So we append each of these to our current path and add these new paths to the queue. Now q looks like [[0, 1], [0, 2]].

We repeat these steps until the queue is empty:

Process [0, 1]. This path ends in 1, which is not the target.
- Check neighbors of 1, which only includes [3].
- Append 3 to our path, resulting in [0, 1, 3], and add it to the ans list since 3 is the target. Queue q is now [[0, 2]].
Process [0, 2]. This path ends in 2, which is not the target.
- Check neighbors of 2, which only includes [3].
- Append 3 to our path, resulting in [0, 2, 3], and add it to the ans list. The queue q is now empty.

Now that the queue q is empty, we’ve finished exploring all paths, and the process is complete. The list ans contains all complete paths: ans = [[0, 1, 3], [0, 2, 3]].

Each list within ans represents a distinct path from node 0 to node 3. Hence, the paths are:

Path 1: 0 -> 1 -> 3
Path 2: 0 -> 2 -> 3

These two paths represent all the unique paths through the graph from the start node to the end node, and this is the final answer returned by the BFS approach.

Solution Implementation

1from collections import deque  # Import deque from collections module for efficient queue operations
2
3class Solution:
4    def allPathsSourceTarget(self, graph):
5        # Determine the number of nodes in the graph
6        num_nodes = len(graph)
7
8        # Initialize a queue with the path starting from node 0
9        queue = deque([[0]])
10
11        # List to store all possible paths from source to target
12        all_paths = []
13
14        # Perform Breadth-First Search
15        while queue:
16            # Get the first path from the queue
17            current_path = queue.popleft()
18
19            # Access the last node in the current_path
20            last_node = current_path[-1]
21
22            # If the last node is the target node (last node in graph), append the path to all_paths
23            if last_node == num_nodes - 1:
24                all_paths.append(current_path)
25                continue
26
27            # Explore each neighbor of the last node
28            for neighbor in graph[last_node]:
29                # Append the neighbor to the current path and add the new path to the queue
30                queue.append(current_path + [neighbor])
31
32        # Return the list of all paths from source to target
33        return all_paths
34

1import java.util.*;
2
3class Solution {
4    // Function to find all paths from source (node 0) to target (last node)
5    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
6        int n = graph.length; // The number of vertices in the graph
7        Queue<List<Integer>> queue = new LinkedList<>(); // Queue to hold the paths to be explored
8        queue.offer(Arrays.asList(0)); // Initialize queue with path starting from node 0
9        List<List<Integer>> allPaths = new ArrayList<>(); // List to store all the paths from source to target
10      
11        // Process paths in the queue
12        while (!queue.isEmpty()) {
13            List<Integer> path = queue.poll(); // Retrieve and remove the head of the queue
14            int lastNode = path.get(path.size() - 1); // Get the last node in the path
15          
16            // If the last node is the target, add the path to the result
17            if (lastNode == n - 1) {
18                allPaths.add(path);
19            } else {
20                // Explore all the neighbors of the last node
21                for (int neighbor : graph[lastNode]) {
22                    List<Integer> newPath = new ArrayList<>(path); // Make a copy of the current path
23                    newPath.add(neighbor); // Add neighbor to the new path
24                    queue.offer(newPath); // Add the new path to the queue
25                }
26            }
27        }
28      
29        return allPaths; // Return the list of all paths from source to target
30    }
31}
32

1#include <vector>
2
3using namespace std;
4
5class Solution {
6public:
7    vector<vector<int>> adjacencyList; // Graph representation as an adjacency list
8    vector<vector<int>> allPaths; // To store all paths from source to target
9
10    // Function to find all paths from source to target in a directed graph
11    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
12        adjacencyList = graph; // Initialize the adjacency list with the graph
13        vector<int> currentPath; // Current path being explored
14        currentPath.push_back(0); // Start from node 0, as per problem statement
15        depthFirstSearch(0, currentPath); // Begin DFS from node 0
16        return allPaths; // Return all the computed paths after DFS completion
17    }
18
19    // Recursive function to perform depth-first search
20    void depthFirstSearch(int nodeIndex, vector<int> currentPath) {
21        // Base case: If the current node is the last node in the graph
22        if (nodeIndex == adjacencyList.size() - 1) {
23            allPaths.push_back(currentPath); // Add current path to all paths
24            return; // End recursion
25        }
26
27        // Recursive case: Explore all the adjacent nodes
28        for (int adjacentNode : adjacencyList[nodeIndex]) {
29            currentPath.push_back(adjacentNode); // Add adjacent node to current path
30            depthFirstSearch(adjacentNode, currentPath); // Recurse with new node
31            currentPath.pop_back(); // Remove the last node to backtrack
32        }
33    }
34};
35

1// Define the function to find all paths from the source (node 0) to the target (last node).
2// This function takes a graph represented as an adjacency list and returns an array of paths.
3// The graph is an array where graph[i] contains a list of all nodes that node i is connected to.
4function allPathsSourceTarget(graph: number[][]): number[][] {
5    // Initialize the array to hold all possible paths.
6    const paths: number[][] = [];
7    // Create a temporary path starting with node 0 (the source).
8    const path: number[] = [0];
9
10    // Define the depth-first search function.
11    // The 'currentPath' parameter represents the current path being explored.
12    const dfs = (currentPath: number[]) => {
13        // Get the last node from the current path.
14        const currentNode: number = currentPath[currentPath.length - 1];
15        // Check if the current node is the target node (last node in the graph).
16        if (currentNode === graph.length - 1) {
17            // If we've reached the target, add a copy of the current path to the paths array.
18            paths.push([...currentPath]);
19            return;
20        }
21        // Iterate over all neighboring nodes connected to the current node.
22        for (const nextNode of graph[currentNode]) {
23            // Add the neighbor node to the current path.
24            currentPath.push(nextNode);
25            // Recursively call 'dfs' with the updated path.
26            dfs(currentPath);
27            // Backtrack: remove the last node from the path to explore other paths.
28            currentPath.pop();
29        }
30    };
31
32    // Start the depth-first search with the initial path.
33    dfs(path);
34    // Return all the paths found.
35    return paths;
36}
37

Time and Space Complexity

The provided code is designed to find all paths from the source node (0) to the target node (n - 1) in a directed acyclic graph (DAG). Here is an analysis of its time and space complexity:

Time Complexity

The worst-case time complexity is determined by the number of paths and the operations performed on each path. In the worst case, each node except the last can have an edge to every other node, resulting in an exponential number of paths, specifically O(2^(n-1)), where n is the number of nodes (since each node can be included or not in a path, like a binary decision).

A new list is created for every new path with the operation path + [v], which takes O(k) time, where k is the length of the current path.

Therefore, the overall worst-case time complexity is O(2^n * n), because there could be 2^n paths and each path could take up to n time to be copied.

Space Complexity

The space complexity is influenced by two factors:

The space needed to store all possible paths (ans).
The additional space needed for the queue (q) to store intermediate paths.

In the worst case, all possible paths from the source to the target are stored in ans, and each path can be of length n, leading to a space complexity of O(2^n * n).

The queue will also store a considerable amount of paths. However, this does not exceed the space complexity for storing all paths since it's essentially a part of the same process.

So, the space complexity of the algorithm is O(2^n * n).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know