Katkat
Back

Enumerate All Simple Directed Paths

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests graph traversal techniques, specifically depth-first search (DFS) with backtracking to identify all unique simple paths in a directed graph.

Problem Statement

Given a directed graph represented as an adjacency list, find all simple paths starting from a source node start to a target node end. A simple path is a path that does not contain repeated vertices.

You must return the list of all such paths sorted in lexicographical order. If no path exists, return an empty list.

Function Signature

def find_all_paths(graph: dict[int, list[int]], start: int, end: int) -> list[list[int]]:

Constraints

  • The graph may contain cycles.
  • The number of vertices V is up to 20.
  • The graph is represented as a dictionary where graph[u] is a list of neighbors of u.

Examples

Example 1: Input: graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: []}, start = 0, end = 3 Output: [[0, 1, 2, 3], [0, 2, 3]] Explanation: Path [0, 1, 2, 0, ...] is not simple, so it is excluded.

Example 2: Input: graph = {0: [1], 1: [2], 2: []}, start = 0, end = 2 Output: [[0, 1, 2]]

Edge Cases

  • The start node is the same as the end node (a path of length 0 or a cycle).
  • Disconnected components or no path existing between start and end.
  • A graph consisting of a single node.

Hints

Hint 1

Use a depth-first search (DFS) approach to explore paths starting from the source node.

Hint 2

Maintain a 'visited' set during the recursion to ensure that you do not visit the same node twice within a single path (enforcing the simple path constraint).

Hint 3

Once the recursion reaches the target node, add the current path to your results list; ensure you backtrack by removing the node from the visited set after returning from the recursive call.

Follow-up questions

  • How would you modify the algorithm if you only needed to count the total number of simple paths instead of enumerating them?
  • What is the time complexity of your solution in the worst-case scenario (e.g., a complete directed graph)?
  • If the graph were extremely large and the number of paths exceeded memory limits, how would you approach finding just the shortest path?