LeetCode Solutions Blog

Number of Restricted Paths From First to Last Node

Difficulty: Medium

Problem Description

You are given an undirected weighted connected graph with n nodes and an array of edges. Each edge connects two nodes with a certain weight. A restricted path from node 1 to node n is defined as a path where each subsequent node in the path has a shorter distance to node n than the previous node. Your task is to find the number of restricted paths from node 1 to node n, returning the result modulo 10^9 + 7.

Key Insights

Use Dijkstra's algorithm to determine the shortest distance from each node to node n.
A restricted path requires that the distance to the last node must be strictly greater than the distance to the next node along the path.
Dynamic programming can be employed to count the number of valid paths satisfying the restriction.

Space and Time Complexity

Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices. This is due to using Dijkstra's algorithm for shortest path calculation and a graph traversal for counting paths.

Space Complexity: O(V + E), for storing the graph representation and maintaining the distance and path count arrays.

Solution

To solve this problem, we can follow these steps:

Construct the graph using an adjacency list from the given edges.
Use Dijkstra's algorithm to compute the shortest distance from every node to node n.
Implement a depth-first search (DFS) or dynamic programming approach to count the restricted paths from node 1 to node n, ensuring that we only follow paths that maintain the distance restriction.

Code Solutions

import heapq
from collections import defaultdict

def countRestrictedPaths(n, edges):
    # Create a graph as an adjacency list
    graph = defaultdict(list)
    for u, v, weight in edges:
        graph[u].append((v, weight))
        graph[v].append((u, weight))
    
    # Dijkstra's algorithm to find shortest path from all nodes to node n
    def dijkstra(start):
        dist = [float('inf')] * (n + 1)
        dist[start] = 0
        min_heap = [(0, start)]
        
        while min_heap:
            current_dist, current_node = heapq.heappop(min_heap)
            if current_dist > dist[current_node]:
                continue
            
            for neighbor, weight in graph[current_node]:
                distance = current_dist + weight
                if distance < dist[neighbor]:
                    dist[neighbor] = distance
                    heapq.heappush(min_heap, (distance, neighbor))
        
        return dist
    
    distances = dijkstra(n)
    
    # Dynamic programming to count restricted paths
    MOD = 10**9 + 7
    dp = [0] * (n + 1)
    dp[n] = 1  # There's one way to be at the last node
    
    # We need to process nodes in the order of their distance to node n
    nodes_by_distance = sorted(range(1, n + 1), key=lambda x: distances[x])
    
    for node in nodes_by_distance:
        for neighbor, weight in graph[node]:
            if distances[neighbor] > distances[node]:  # Check the restriction
                dp[node] = (dp[node] + dp[neighbor]) % MOD
    
    return dp[1]

# Example usage
print(countRestrictedPaths(5, [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]))  # Output: 3