All Paths From Source to Target

All Paths From Source to Target Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order. The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

1. Important part here is to think about the queue and its type, here queue contains listofCurrentPaths
2. Iterate over the queue to find out when it gets empty means there are no more paths left
3. After this approach there will many paths (longer and shorter printed from source to destination)
4. Add path to the final list when you see last element in list == destination (many atime destination is graph.length -1)

public List<List>> allPathsSourceToDestination(int[][] graph) {
      //create adjacency list which contains all paths
      Queue<List<Integer>> queueForPaths = new LinkedList<>();
      List<List<Integer>> resultsPath = new ArrayList<>();

        queueForPaths.add(Arrays.asList(0));
        while (!queueForPaths.isEmpty()) {
            List<Integer> listOfPaths = queueForPaths.remove();

            int lastNode = listOfPaths.get(listOfPaths.size()-1);
            if(lastNode == target) {
                System.out.println("We found a path : ");
                resultsPath.add(listOfPaths);
             } else {
                for (int neighbour : mp.get(lastNode)){
                    List<Integer> newPath = new ArrayList<>(listOfPaths);
                    newPath.add(neighbour);
                    queueForPaths.add(newPath);
                }
            }
        }
        return resultsPath;
    }