All Paths from Source Lead to Destination

All Paths from Source Lead to Destination

What is this problem about?

The "All Paths from Source Lead to Destination interview question" is a graph problem where you must verify a strict condition: every possible path starting from a given source node must eventually end at a specific destination node. Furthermore, the destination node itself must be a "dead end" (no outgoing edges), and the graph should not contain any cycles that could trap a path forever before it reaches the destination.

Why is this asked in interviews?

Google uses the "All Paths from Source Lead to Destination coding problem" to test a candidate's ability to perform exhaustive graph validation. It's not enough to find one path; you must ensure every path is valid. This involves detecting cycles and identifying nodes that have no exit or lead to an incorrect endpoint. It tests your mastery of recursion and state management during traversals.

Algorithmic pattern used

This problem is solved using the Depth-First Search (DFS) with State Coloring pattern.

• Three Colors/States:
  • 0 (Unvisited): Node has not been explored.
  • 1 (Visiting): Node is in the current recursion stack (used to detect cycles).
  • 2 (Visited): Node has been fully explored and all its paths are confirmed to lead to the destination. For every node, you check:

1. If it's a leaf, it must be the destination.
2. If it's not a leaf, all its neighbors must eventually lead to the destination.
3. If you encounter a node in the Visiting state, you've found a cycle, meaning not all paths reach the destination.

Example explanation

Nodes: 0, 1, 2. Source: 0, Destination: 2. Edges: 0 -> 1, 1 -> 2, 1 -> 0.

• Start at 0: Mark 0 as Visiting. Move to neighbor 1.
• At 1: Mark 1 as Visiting. Neighbors are 2 and 0.
• Check neighbor 0: 0 is already Visiting! This is a cycle. Result: False, because a path can loop 0 -> 1 -> 0 forever and never reach 2.

Common mistakes candidates make

• Only checking reachability: Successfully reaching the destination once doesn't mean all paths lead there.
• Missing the "Dead End" rule: Forgetting that the destination itself must not have any outgoing edges.
• Ignoring Cycles: Failing to use a visiting state to catch infinite loops in the graph.

Interview preparation tip

When a problem mentions "all paths," think about how to use DFS to validate every branch. If "infinite paths" are a possibility, cycle detection (the "three-color" DFS) is almost always the required pattern. Practice identifying when a graph problem requires simple traversal versus full path validation.