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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Restricted Paths From First to Last Node

Number: 1912

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an undirected weighted connected graph with n nodes (labeled 1 to n) and an edge list where each edge connects two nodes with a given weight, determine the number of restricted paths from node 1 to node n. A restricted path is defined as a path where for every consecutive pair of nodes in the path, the shortest distance (using edge weights) from the current node to node n is strictly greater than that from the next node to node n. Return the count modulo 10^9 + 7.

Key Insights

  • Use Dijkstra's algorithm starting from node n to compute the shortest distance from every node to node n.
  • A restricted path can only move in the direction of strictly decreasing distance values, forming a kind of “topological” order.
  • Dynamic Programming (or DFS with memoization) can be used to count the number of valid paths from node 1 to node n.
  • Modulo arithmetic (MOD = 10^9 + 7) must be applied to handle large counts.

Space and Time Complexity

Time Complexity: O(E log N) for Dijkstra's algorithm + O(N + E) for the DP/DFS traversal, overall O(E log N). Space Complexity: O(N + E) for storing the graph and additional data structures for distances and memoization.

Solution

We first run Dijkstra's algorithm from the destination node n to calculate the shortest distance from every node to node n. With these distances, we can then perform a DFS (or iterative DP) starting from node 1. During this DFS, for each node we traverse only those neighbors that have a strictly smaller distance to node n than the current node. We memoize each count to avoid redundant computations. The result is then returned modulo 10^9 + 7.

Code Solutions

import heapq

MOD = 10**9 + 7

def countRestrictedPaths(n, edges):
    # Build graph from edge list
    graph = {i: [] for i in range(1, n+1)}
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # Dijkstra's algorithm to compute shortest path from node n to all nodes
    dist = [float('inf')] * (n + 1)
    dist[n] = 0
    min_heap = [(0, n)]
    
    while min_heap:
        d, node = heapq.heappop(min_heap)
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            if d + weight < dist[neighbor]:
                dist[neighbor] = d + weight
                heapq.heappush(min_heap, (dist[neighbor], neighbor))
    
    # Memoization array for DFS dynamic programming
    memo = {}
    
    def dfs(node):
        # If reached destination, return 1 path
        if node == n:
            return 1
        if node in memo:
            return memo[node]
        total_paths = 0
        # Traverse only neighbors with strictly smaller distance value
        for neighbor, weight in graph[node]:
            if dist[node] > dist[neighbor]:
                total_paths = (total_paths + dfs(neighbor)) % MOD
        memo[node] = total_paths
        return total_paths
        
    return dfs(1)

# Example usage:
n = 5
edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
print(countRestrictedPaths(n, edges))  # Output: 3
← Back to All Questions