We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

All Paths from Source Lead to Destination

Number: 511

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a directed graph (which may include self-loops and parallel edges) represented by a list of edges, and two specified nodes (source and destination), determine if every possible path starting from the source eventually ends at the destination. In other words, from the source:

  • There must be at least one valid path to the destination.
  • Any path that terminates at a node with no outgoing edges must end at the destination.
  • There must be a finite number of paths leading to the destination (i.e. avoid infinite cycles).

Key Insights

  • Build an adjacency list to represent the graph.
  • Use Depth First Search (DFS) to explore all possible paths from the source.
  • For any node with no outgoing edges, ensure that it is the destination.
  • Employ cycle detection (using a state array or coloring) to detect and avoid infinite loops.
  • Use memoization (marking nodes as safe) to avoid re-processing nodes.

Space and Time Complexity

Time Complexity: O(V + E) in the worst-case, where V is the number of vertices and E is the number of edges. Space Complexity: O(V + E) due to the recursion stack (or iterative stack) and the storage required for the graph's adjacency list.

Solution

We solve the problem by running a DFS starting from the source. At each step:

  1. If the current node has no outgoing edges, verify that it is the destination.
  2. Otherwise, recursively explore each neighbor. If any path does not lead exclusively to the destination, return false.
  3. Use a state-array with three states (0 = unvisited, 1 = visiting, 2 = visited) to detect cycles. A cycle (state of 1) implies there is a possibility for an infinite path, so we return false.
  4. Memoize results by marking nodes as fully processed (state = 2) once all their paths are verified.

Code Solutions

# Function to determine if all paths from source lead to destination
def leadsToDestination(n, edges, source, destination):
    # Build the adjacency list for the graph
    graph = { i: [] for i in range(n) }
    for u, v in edges:
        graph[u].append(v)
        
    # States: 0 = unvisited, 1 = visiting, 2 = visited (fully processed)
    state = [0] * n

    # Helper DFS function with cycle detection and path validation
    def dfs(node):
        # If node is a leaf, it must be the destination
        if not graph[node]:
            return node == destination
        # If node is in the process of visiting, a cycle is detected
        if state[node] == 1:
            return False
        # If already fully visited, no need to reprocess
        if state[node] == 2:
            return True
        
        state[node] = 1  # Mark node as visiting
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        state[node] = 2  # Mark node as visited once all paths are verified
        return True

    # Start DFS from the source node
    return dfs(source)

# Example usage:
#print(leadsToDestination(4, [[0,1],[0,2],[1,3],[2,3]], 0, 3))  # Expected output: True
← Back to All Questions