All Paths From Source to Target

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);
    }
};

This solution provides an efficient way to find all possible paths from the source node to the target node in a directed graph using C++.

• The findPaths function takes a 2D vector graph as input, representing the adjacency list of the graph.

• A Depth First Search (DFS) approach with memoization is used to traverse the graph. Memoization caches results of subproblems to optimize performance and avoid recomputation.

• The algorithm utilizes a recursive lambda function dfs that captures local variables by reference.

  • This function checks the cache for previously computed paths from the current node. If found, it immediately returns the cached paths.
  • If a path reaches the target node (identified by lastNode), it returns a path containing only this node.
  • For other nodes, it iterates through all neighbors, recursively calls dfs for each neighbor to get all paths from that neighbor to the target, and appends the current node to each of these paths.

• Results from recursive calls are stored in the cache to ensure that each node's paths are computed once.

• Finally, the function initiates the DFS from the source node (node 0) and returns all possible paths to the target node.

This approach is especially powerful for complex graphs as it significantly minimizes the number of computations needed by reusing the results stored in the cache. The usage of vectors and dynamic memory ensures that the solution adapts to the size and complexity of the input graph dynamically.

class Solution {
    private int destinationNode;
    private int[][] adjacencyList;
    private HashMap<Integer, List<List<Integer>>> cachedResults;

    protected List<List<Integer>> traverseAllPaths(int startNode) {
        if (cachedResults.containsKey(startNode))
            return cachedResults.get(startNode);

        List<List<Integer>> paths = new ArrayList<>();
        if(startNode == this.destinationNode) {
            ArrayList<Integer> singlePath = new ArrayList<>();
            singlePath.add(destinationNode);
            paths.add(singlePath);
            return paths;
        }

        for(int nextNode : this.adjacencyList[startNode]) {
            for(List<Integer> subPath : traverseAllPaths(nextNode)) {
                ArrayList<Integer> extendedPath = new ArrayList<>();
                extendedPath.add(startNode);
                extendedPath.addAll(subPath);
                paths.add(extendedPath);
            }
        }
        cachedResults.put(startNode, paths);
        return paths;
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.destinationNode = graph.length - 1;
        this.adjacencyList = graph;
        this.cachedResults = new HashMap<>();

        return this.traverseAllPaths(0);
    }
}

This summary explains the Java solution for finding all paths from a source node to a destination node in a directed graph. The solution class named Solution uses Depth-First Search (DFS) and memoization technique for efficient traversal.

• In the Solution class, few private properties are initialized:

  • destinationNode to hold the value of the last node in the graph.
  • adjacencyList to contain the graph represented as an adjacency list.
  • cachedResults to store already computed paths from any given node to the destination, improving the efficiency by avoiding redundant calculations.

• The primary method allPathsSourceTarget is the entry point:

  • It initializes destinationNode, adjacencyList, and cachedResults.
  • Calls traverseAllPaths with the source node, which is always node 0 in this problem.

• The traverseAllPaths function executes the DFS:

  • First, it checks if the start node's paths are already calculated using cachedResults.
  • If at the destinationNode, it returns a path containing only this node.
  • For each node, it recursively traverses all paths from its adjacent nodes using traverseAllPaths. The paths found are then extended by adding the start node at the beginning.
  • The final list of paths for the start node is cached before the method returns it.

This recursive approach, combined with memoization, ensures that the function runs efficiently without recomputation of paths for any node, ultimately returning all possible paths from the source to the target in a directed graph.

class Solution:
    def pathsFromStartToEnd(self, graph: List[List[int]]) -> List[List[int]]:
        end_node = len(graph) - 1
        
        @lru_cache(maxsize=None)
        def find_paths(node):
            if node == end_node:
                return [[end_node]]

            paths = []
            for adjacent in graph[node]:
                for subsequent_path in find_paths(adjacent):
                    paths.append([node] + subsequent_path)

            return paths

        return find_paths(0)

This Python solution tackles the problem of finding all possible paths from the source node to the target node in a directed graph. The graph is given as an adjacency list, where the index of the list represents the source node and each sublist contains the nodes that the source node is directly connected to.

Here's a concise explanation of the approach applied in the code:

• Define a method pathsFromStartToEnd within the Solution class that accepts a graph represented as a list of lists.
• Determine the target node by obtaining the length of the graph list minus one.
• Use a decorated helper function find_paths with an LRU (Least Recently Used) cache to store the results of subproblems, enhancing the efficiency of the solution.
• Within the helper function:
  • Return a path containing only the end_node if the current node is the end_node.
  • Initialize an empty list to collect paths.
  • Iterate over nodes adjacent to the current node, recursively calling find_paths to find paths from each adjacent node to the end_node.
  • Concatenate the current node with each path obtained from the recursive calls and append the full path to the paths list.
• Finally, the method returns the result of invoking find_paths from the source node, which is node 0.

This approach uses recursion efficiently with memoization (via lru_cache) to avoid redundant computations, ensuring that the algorithm performs optimally even for larger graphs.