All Paths From Source to Target

Problem Statement

In the context of graph theory, specifically working with a directed acyclic graph (DAG), where nodes represent states or positions and edges represent possible transitions between these nodes, the problem here is to enumerate all paths from a starting node (0) to an ending node (n - 1). The DAG is described by n nodes, each labeled sequentially from 0 to n - 1. Each node i in this graph has a list graph[i], which contains all the nodes that can be reached directly from i through a directed edge. Given this setup, the task is to find and return every possible path that leads from node 0 to node n - 1.

Examples

Example 1

Input:

graph = [[1,2],[3],[3],[]]

Output:

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

Explanation:

There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2

Input:

graph = [[4,3,1],[3,2,4],[3],[4],[]]

Output:

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

Constraints

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i (i.e., there will be no self-loops).
• All the elements of graph[i] are unique.
• The input graph is guaranteed to be a DAG.

Approach and Intuition

Based on the problem's constraints and the examples provided, the approach can be broken down as follows:

1. Depth-First Search (DFS) Method:

   • Initiate a recursive search from the starting node (0), keeping track of the path you're currently exploring.
   • If the current node is the target node (n - 1), append the current path to the list of result paths.
   • Otherwise, iterate over the adjacent nodes and explore each recursively.
   • After exploring all paths from the current node, backtrack to explore new possible paths from previous nodes.

2. Graph Constraints Usefulness:

   • Since the graph is guaranteed to be a DAG (directed acyclic graph), there is no need to worry about cycles, which simplifies the DFS as it eliminates the case where a path loops back onto itself.
   • The problem ensures that all nodes are reachable and paths are unique through the constraints that graph[i][j] will always be unique and can't be i.

3. Path Finding in Small Graphs:

   • Given the constraint of n (up to 15), this allows for a DFS without significant concern about performance, since the maximum size is still manageable for a complete search of all paths.

4. Working with Examples:

   • Example 1: The graph [[1,2],[3],[3],[]] translates to node 0 connected to nodes 1 and 2, both of which directly point to 3, the final node. Two paths are direct and straightforward: 0 -> 1 -> 3 and 0 -> 2 -> 3.
   • Example 2: This graph showcases a more complex structure with multiple ways reaching the end, indicating that the DFS approach needs to robustly backtrack to explore all these potential paths, such as 0 -> 4, 0 -> 3 -> 4, and so on through various combinations.

Through the use of DFS, harnessing the properties of a DAG, and leveraging Python's list and recursion capabilities, this problem of finding all paths in a small-scale DAG becomes an exercise in careful implementation of graph traversal techniques.

Solutions

class Solution {
public:
    vector<vector<int>> findPaths(vector<vector<int>>& graph) {
        int lastNode = int(graph.size()) - 1;
        map<int, vector<vector<int>>> cache;
        function<vector<vector<int>>(int)> dfs = [&](int currentNode) {
            if (cache.count(currentNode)) return cache[currentNode];
            vector<vector<int>> paths;
            if (currentNode == lastNode) {
                paths.push_back(vector<int>{lastNode});
            } else {
                for (int neighbor : graph[currentNode]) {
                    for (vector<int>& path : dfs(neighbor)) {
                        vector<int> newPath{currentNode};
                        newPath.insert(newPath.end(), path.begin(), path.end());
                        paths.push_back(newPath);
                    }
                }
            }
            cache[currentNode] = paths;
            return paths;
        };
        return dfs(0);
    }
};