All Paths From Source To Target - Leetcode Solution

In this blog post, we’ll explore a problem commonly encountered in graph theory: finding all possible paths from a source node to a target node in a directed graph. We’ll break down the problem, discuss a solution, and provide a code implementation using Depth-First Search (DFS).

Problem Description

Given a directed acyclic graph (DAG) represented as an adjacency list, you need to find all possible paths from the source node (node 0) to the target node (the last node in the list). Each node in the graph is represented as an index, and the adjacency list describes the edges connecting the nodes.

Example Input:

adjacencyList = [[1,2],[3],[3],[]]` 

This graph can be visualized as follows:

0 -> 1
0 -> 2
1 -> 3
2 -> 3` 

The target node here is node 3, and the goal is to find all paths from node 0 to node 3.

Expected Output:

[[0, 1, 3], [0, 2, 3]]

These are the two distinct paths from node 0 to node 3.

Solution Approach

To solve this problem, we’ll use Depth-First Search (DFS) to explore all possible paths from the source node to the target node. We’ll maintain a path list to track the current path being explored and a result list to store all valid paths once the target is reached.

Here’s the step-by-step approach:

1. Build the Graph: Convert the adjacency list into a graph representation where each node maps to its list of neighbors.
2. Perform DFS: Start DFS from the source node. For each node, explore its neighbors recursively, building paths until the target node is reached.
3. Backtrack: After exploring all paths from a node, backtrack to explore other potential paths.

Code Implementation

Below is the JavaScript code that implements the described approach:

const allPathsSourceTarget = function(adjacencyList) {
    // Convert adjacency list into a graph representation
    const graph = buildGraphFromAdjacencyList(adjacencyList);
    const result = [];
    const target = adjacencyList.length - 1; // The target is always the last node in the list

    // Depth-First Search (DFS) function to explore paths
    const dfs = (node, path) => {
        // Add the current node to the path
        path.push(node);

        // Check if the target node is reached
        if (node === target) {
            result.push([...path]); // Store a copy of the current path
        } else {
            // Explore neighbors
            for (let nb of graph[node]) {
                dfs(nb, path);
            }
        }
        
        // Backtrack to explore other paths
        path.pop();
    };

    // Start DFS from the source node (0)
    dfs(0, []);
    return result;
};

Helper function to build the graph from an adjacency list

const buildGraphFromAdjacencyList = (adjacencyList) => {
    let graph = {};
    
    for (let i = 0; i < adjacencyList.length; i++) {
        graph[i] = adjacencyList[i];
    }
    
    return graph;
};

Explanation of the Code

1. Building the Graph:

   • buildGraphFromAdjacencyList function converts the adjacency list into a graph where each node index maps to its list of neighbors.

2. DFS Traversal:

   • The dfs function recursively explores paths from the current node to its neighbors. It adds nodes to the current path, checks if the target is reached, and stores the path if valid.
   • After exploring all neighbors, it backtracks by removing the last node from the path to explore other potential paths.

3. Starting the Search:

   • The search starts from node 0 with an empty path. The results are collected and returned after the DFS completes.

Conclusion

Finding all paths from the source to the target node in a directed graph can be efficiently solved using DFS. By maintaining a path list and utilizing backtracking, we can explore all potential paths and identify those that reach the target node. This approach is effective for solving problems involving pathfinding in graphs and can be adapted for various similar challenges.