Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: All Paths From Source to Target
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a directed acyclic graph (DAG) with 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.

Examples

Example 1

  • Input: graph = [[2,3],[3,4],[3,4],[4],[]]
Image
  • Expected Output: [[0,2,3,4],[0,2,4],[0,3,4]]
  • Justification: You can go from node 0 to 4 via 2 and 3 or only 2 or only 3.

Example 2

  • Input: graph = [[1,3,4],[2,4],[3],[],[2,3]]
Image
  • Expected Output: [[0,1,4],[0,4]]
  • Justification: You can go from node 0 to 4 via 1 or directly.3`.

Example 3

  • Input: graph = [[1,2,3],[2,3,4],[3,4],[],[3]]
  • Expected Output: [[0,1,2,4],[0,1,4],[0,2,4]]
  • Justification: There are total 3 paths from node 0 to 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.

Solution

To solve this problem, we can use Depth-First Search (DFS). DFS is suitable because it explores each path from the start to the target, making it possible to backtrack and find all potential paths. In this case, we start from node 0 and explore all possible nodes we can reach, storing each valid path until we reach the target node (n-1).

This approach ensures that we explore all routes from the source to the target. Using DFS is effective here as it allows us to traverse deep into each potential path and then backtrack to explore other paths.

Step-by-Step Algorithm

  1. Initialize Result List: Create a list result to store all the paths from the source to the target.
  2. Initialize Path List: Create a list path and add the starting node (0) to it.
  3. Define DFS Function: Define a Depth-First Search (DFS) function that takes the current node, the current path, and the result list as arguments.
  4. Check if Target Node is Reached:
    • If the current node is the target node (n-1), add the current path to the result list and return.
  5. Explore Adjacent Nodes:
    • Iterate through each node in graph[current_node] (the nodes that can be visited from the current node).
    • For each adjacent node:
      • Add the node to the current path.
      • Recursively call the DFS function with the new node and updated path.
      • Remove the last node from the path to backtrack and explore other paths.
  6. Call DFS from Source Node: Call the DFS function with the starting node (0), the initial path, and the result list.
  7. Return Result: After the DFS function completes, return the result list containing all paths from the source to the target.

Algorithm Walkthrough

Given the input graph = [[2,3],[3,4],[3,4],[4],[]]:

Image

  1. Initialize Result and Path Lists:

    • result = []
    • path = [0]

  2. Start DFS from Node 0:

    • dfs(0, [0], result)

  3. DFS at Node 0:

    • path = [0]
    • Adjacent nodes: 2, 3
    • For node 2:
      • Add node 2 to path: path = [0, 2]
      • Call dfs(2, [0, 2], result)

  4. DFS at Node 2:

    • path = [0, 2]
    • Adjacent nodes: 3, 4
    • For node 3:
      • Add node 3 to path: path = [0, 2, 3]
      • Call dfs(3, [0, 2, 3], result)

  5. DFS at Node 3:

    • path = [0, 2, 3]
    • Adjacent nodes: 4
    • For node 4:
      • Add node 4 to path: path = [0, 2, 3, 4]
      • Call dfs(4, [0, 2, 3, 4], result)

  6. DFS at Node 4 (Target Node):

    • path = [0, 2, 3, 4]
    • Add path to result: result = [[0, 2, 3, 4]]
    • Backtrack: remove node 4 from path: path = [0, 2, 3]

  7. Backtrack to Node 2:

    • path = [0, 2]
    • For node 4:
      • Add node 4 to path: path = [0, 2, 4]
      • Call dfs(4, [0, 2, 4], result)

  8. DFS at Node 4 (Target Node):

    • path = [0, 2, 4]
    • Add path to result: result = [[0, 2, 3, 4], [0, 2, 4]]
    • Backtrack: remove node 4 from path: path = [0, 2]

  9. Backtrack to Node 0:

    • path = [0]
    • For node 3:
      • Add node 3 to path: path = [0, 3]
      • Call dfs(3, [0, 3], result)

  10. DFS at Node 3:

    • path = [0, 3]
    • Adjacent nodes: 4
    • For node 4:
      • Add node 4 to path: path = [0, 3, 4]
      • Call dfs(4, [0, 3, 4], result)

  11. DFS at Node 4 (Target Node):

    • path = [0, 3, 4]
    • Add path to result: result = [[0, 2, 3, 4], [0, 2, 4], [0, 3, 4]]
    • Backtrack: remove node 4 from path: path = [0, 3]

  12. Backtrack to Node 0:

    • path = [0]
    • All adjacent nodes of node 0 have been explored.

  13. DFS Complete:

    • Return result: [[0, 2, 3, 4], [0, 2, 4], [0, 3, 4]]

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: The time complexity of this algorithm is O(2^n \cdot n). This is because in the worst case, each node has an edge to every other node, leading to an exponential number of paths, and we are storing each path, which takes O(n) time for each path.

  • Space Complexity: The space complexity is O(2^n \cdot n) as well. This is due to the storage required for the result list, which can store up to 2^n paths, each of which is of length (n).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible