Find All Paths From Source to Target

Edit PagePage History

Unit 12 Session 2 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
  
• ⏰ Time to complete: 20-30 mins
  
• 🛠️ Topics: Graphs, DFS, Backtracking
  

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What kind of graph is this?

  • A Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n-1.

• What should be returned?

  • All paths from the source node 0 to the target node n-1.

HAPPY CASE
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: Two paths exist: 0 -> 1 -> 3 and 0 -> 2 -> 3.

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]]
Explanation: Multiple valid paths from 0 to 4.

EDGE CASE
Input: graph = [[1],[]]
Output: [[0,1]]
Explanation: Only one path exists from 0 to 1.

Input: graph = [[]]
Output: [[0]]
Explanation: The graph only contains the source node 0.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Graph Traversal and Pathfinding Problems, we can consider the following approaches:

• DFS (Depth-First Search): Explore all paths from the source to the target.
• Backtracking: Add and remove nodes during traversal to explore all possible paths.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS with Backtracking to explore all paths from node 0 to node n-1. Whenever we reach the target node, store the path. Use backtracking to ensure all possible paths are explored.

1) Initialize an empty list `result` to store all valid paths.
2) Define a helper function `dfs(node, path)`:
   a) If `node` is the target node (n-1), add the path to the result.
   b) For each neighbor of the current node, recursively call `dfs` with the neighbor.
   c) After the recursive call, backtrack by removing the last node from the path.
3) Call `dfs` with the starting node `0` and path `[0]`.
4) Return `result`.

⚠️ Common Mistakes

• Forgetting to backtrack by removing the last node from the path.
• Not handling the case when the graph has only one node.

4: I-mplement

Implement the code to solve the algorithm.

def all_paths(graph):
    result = []
    
    def dfs(node, path):
        if node == len(graph) - 1:
            result.append(path[:])
            return
        for neighbor in graph[node]:
            path.append(neighbor)
            dfs(neighbor, path)
            path.pop()

    dfs(0, [0])
    return result

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: graph = 1,2],[3],[3],[

  • Path exploration: [0] -> [0,1] -> 0,1,3
  • Backtrack to [0] -> [0,2] -> 0,2,3
  • Output: 0,1,3],[0,2,3

• Input: graph = 4,3,1],[3,2,4],[3],[4],[

  • Path exploration yields multiple paths, including [0,1,4] and [0,1,2,3,4].
  • Output: 0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume V is the number of nodes and E is the number of edges.

• Time Complexity: O(V + E) since we visit every node and edge during traversal.
  
• Space Complexity: O(V) due to the recursion stack and storing paths.