Problem Statement:

Given a directed, acyclic graph of N nodes. Find out if all nodes from source lead to a destination node through some path(s). Also, print all the possible paths from the source node to the destination node.

Solution:

The problem can be solved using Depth First Search (DFS) algorithm. We traverse the graph from the source node to all the reachable nodes using DFS. During the traversal, we maintain a list of visited nodes and the path from the source node to the current node.

The path from the source node to a node is said to be valid if the node is either the destination node or can reach the destination node through some valid path(s).

Algorithm:

1. Initialize a list of visited nodes and a list of the current path with the source node.

2. Traverse the graph starting from the source node using Depth First Search (DFS).

   • If the current node is the destination node then mark the path as valid and print the path.
   • If the current node is already visited, then ignore it and continue the traversal.
   • For each unvisited neighbouring node, add it to the current path and mark it as visited, and continue the DFS recursively.

3. After the traversal, if all the nodes are visited and marked as valid, then return true. Else, return false.

Code in Python:

Node class to store the graph

class Node: def init(self, val): self.val = val self.adj_list = []

def allPathsSourceTarget(graph): """ :type graph: List[List[int]] :rtype: List[List[int]] """ # Create a graph with nodes and edges nodes = {} for i in range(len(graph)): nodes[i] = Node(i) for i in range(len(graph)): for j in graph[i]: nodes[i].adj_list.append(nodes[j])

# Depth First Search (DFS)
def dfs(node, visited, path, target, res):
    # Add the node to visited and path
    visited.add(node.val)
    path.append(node.val)
    
    # If the current node is the destination node
    if node.val == target:
        res.append(path[:])
    else:
        # Traverse all neighbouring nodes
        for n in node.adj_list:
            # Check if the neighbour is already visited
            if n.val not in visited:
                dfs(n, visited, path, target, res)

    # Remove the node from path and visited
    path.pop()
    visited.remove(node.val)

# Initialize visited set and result list
visited = set()
target = len(graph) - 1
res = []

# DFS from the source node
dfs(nodes[0], visited, [], target, res)

# If all nodes are visited and marked as valid, then return True
return res

Time Complexity: O(N^2) where N is the number of nodes in the graph. Space Complexity: O(N^2) where N is the number of nodes in the graph (for storing graph as nodes and edges).

1