All Paths from Source Lead to Destination - Solution & Explanation

Problem Overview: Given a directed graph, a source node, and a destination node, verify that every possible path starting from the source eventually ends at the destination. No path should end at another node, and cycles that allow infinite traversal must not exist.

Approach 1: Brute Force DFS Path Exploration (Exponential time)

Start from the source and recursively explore every outgoing edge using depth‑first search. Track the current path and stop when you reach a node with no outgoing edges. If that terminal node is not the destination, the condition fails. This method effectively enumerates paths and checks each terminal state. Time complexity can grow exponentially in dense graphs because the same subgraphs are explored repeatedly. Space complexity is O(V) for the recursion stack.

Approach 2: DFS with Graph Coloring / Cycle Detection (O(V + E))

Build an adjacency list and run DFS from the source while marking nodes with three states: unvisited, visiting, and safe. When DFS reaches a node with no outgoing edges, it must equal the destination; otherwise return false. If DFS encounters a node marked visiting, a cycle exists, which allows infinite paths and invalidates the requirement. Once all children of a node lead to the destination, mark it safe so future DFS calls reuse the result. This pruning avoids repeated exploration. Time complexity is O(V + E) with O(V) space for recursion and state tracking.

Approach 3: Reverse Graph + Topological Validation (O(V + E))

Another way to reason about the constraint is that every reachable node must eventually flow into the destination without cycles. Build the graph and analyze nodes using ideas from topological sort. Nodes that have no outgoing edges must be the destination; otherwise the condition fails immediately. You can propagate validity backward from the destination through incoming edges. If any reachable node cannot be proven to terminate at the destination, the graph violates the rule. Time complexity remains O(V + E) with O(V + E) space for adjacency structures.

The key insight is that the graph must behave like a directed acyclic funnel into the destination. Cycles break the guarantee because a path could loop forever, and dead-end nodes break it because a path stops before the destination.

Recommended for interviews: DFS with coloring is the expected approach. It shows you understand graph traversal, cycle detection, and memoization. A brute force DFS demonstrates the basic idea but wastes work by revisiting subgraphs. The optimized DFS proves correctness while keeping the complexity linear in the number of vertices and edges.