Number of Restricted Paths From First to Last Node: Dijkstra + DP Pattern

You are given a weighted undirected graph with n nodes labeled 1 through n, and a list of edges with positive weights. Define distanceToLastNode(x) as the shortest path distance from node x to node n. A restricted path from node 1 to node n is a path where distanceToLastNode strictly decreases at each step. Return the number of restricted paths from node 1 to node n, modulo 10^9 + 7.

This is LeetCode 1786: Number of Restricted Paths From First to Last Node, and it teaches a powerful pattern: using shortest-path distances to impose ordering on a graph, then counting paths with DP on the resulting DAG.

Why this problem matters

At first glance, counting paths in a weighted graph sounds intimidating. You might think about trying every possible route, but that is exponential. The breakthrough is realizing that the "strictly decreasing distance" constraint transforms the undirected graph into a directed acyclic graph (DAG).

Once you see that, the problem splits cleanly into two independent phases. Phase one: compute shortest distances from node n using Dijkstra. Phase two: count paths on the resulting DAG using dynamic programming. Each phase uses a well-known algorithm, but combining them is the real insight.

This combination of shortest-path computation followed by DP counting appears in many graph problems. Mastering it here gives you a template you can reuse whenever a problem asks you to count, minimize, or optimize paths subject to a distance-based constraint.

The key insight

Run Dijkstra from node n (not node 1) to compute dist[v] for every node v. Now consider any edge (u, v) in the original graph. You can walk from u to v on a restricted path only if dist[u] > dist[v]. This turns each undirected edge into at most one directed edge, and the resulting directed graph has no cycles because distances strictly decrease along every edge.

With a DAG in hand, you can count paths from node 1 to node n using a simple DP:

• dp[n] = 1 (base case: one way to go from n to itself)
• For every other node u, dp[u] = sum of dp[v] for all neighbors v where dist[u] > dist[v]

Process nodes in order of increasing dist so that when you compute dp[u], all of u's valid neighbors have already been processed.

The solution

import heapq
from collections import defaultdict

def count_restricted_paths(n: int, edges: list[list[int]]) -> int:
    MOD = 10**9 + 7
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))

    dist = [float('inf')] * (n + 1)
    dist[n] = 0
    heap = [(0, n)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    dp = [0] * (n + 1)
    dp[n] = 1
    nodes_by_dist = sorted(range(1, n + 1), key=lambda x: dist[x])

    for u in nodes_by_dist:
        for v, _ in graph[u]:
            if dist[u] > dist[v]:
                dp[u] = (dp[u] + dp[v]) % MOD

    return dp[1]

The code has two clean phases. First, Dijkstra from node n fills the dist array. We use a min-heap and the standard "skip stale entries" optimization. After this phase, dist[v] holds the shortest distance from v to node n for every node.

Second, we sort all nodes by increasing distance. This is our topological order for the DAG formed by the restricted-path constraint. We iterate through this sorted order, and for each node u, we look at every neighbor v. If dist[u] > dist[v], then moving from u to v is a valid step on a restricted path, so we add dp[v] to dp[u]. We take the result modulo 10^9 + 7 at every addition to avoid overflow.

Visual walkthrough

Let's trace through a 5-node graph step by step. We will compute Dijkstra distances from node 5, identify valid restricted transitions, and count paths using DP.

The key observation is in Step 3. By processing nodes from smallest to largest distance, when we reach node 2 (dist=5), nodes 3 (dist=3), 4 (dist=1), and 5 (dist=0) are all already computed. And when we reach node 1 (dist=6), node 2 (dist=5) and node 3 (dist=3) are both ready. The topological ordering falls out naturally from the distance ordering.

Complexity analysis

Time: Dijkstra with a binary heap runs in O((V + E) log V). Sorting nodes takes O(V log V). The DP phase iterates over all edges once, taking O(V + E). The bottleneck is Dijkstra, giving O((V + E) log V) overall.

Space: The adjacency list uses O(V + E). The distance array, DP array, and sorted node list each use O(V). The heap uses O(V) in the worst case. Total: O(V + E).

The building blocks

1. Dijkstra's shortest path

The first building block is running Dijkstra from a single source to compute shortest distances to all other nodes:

dist = [float('inf')] * (n + 1)
dist[source] = 0
heap = [(0, source)]

while heap:
    d, u = heapq.heappop(heap)
    if d > dist[u]:
        continue
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(heap, (dist[v], v))

This is the same Dijkstra you use in Network Delay Time or any single-source shortest-path problem. The "skip stale entries" pattern (if d > dist[u]: continue) avoids processing a node multiple times. The key detail here is that we run it from node n, not node 1, because we need distanceToLastNode values.

2. Path counting with DP on DAG

The second building block is counting paths on a DAG using dynamic programming:

dp[target] = 1
for u in topological_order:
    for v in neighbors_of(u):
        if can_move(u, v):
            dp[u] += dp[v]

This pattern works whenever you can impose a topological ordering on the states. Here, the "can move" check is dist[u] > dist[v], and the topological order comes from sorting by distance. The same DP structure appears in problems like counting paths in a grid, number of ways to reach a target in a DAG, or any problem where you sum up contributions from already-computed sub-problems.

Edge cases

• Node 1 equals node n (n = 1): the only restricted path is the trivial path of length zero. Return 1.
• No path from 1 to n: if the graph is disconnected and node 1 cannot reach node n, dist[1] remains infinity and dp[1] stays 0. Return 0.
• All edges have the same weight: Dijkstra still works correctly. The restricted-path constraint still applies based on the resulting distances.
• Large modular arithmetic: since the answer can be enormous, every addition in the DP phase must be taken modulo 10^9 + 7. Forgetting the mod will cause integer overflow in languages like C++ or Java.
• Multiple edges between the same pair: the graph can have parallel edges. Dijkstra naturally handles this because it always relaxes to the minimum distance. The DP phase processes each edge independently, which is correct.

From understanding to recall

You have seen how Dijkstra distances create a natural DAG and how sorting by distance gives you a topological order for free. The two-phase structure (compute distances, then count paths) makes sense when you read it. But can you reconstruct it under pressure?

The details trip people up. Running Dijkstra from node n instead of node 1. Checking dist[u] > dist[v] (strict inequality, correct direction). Sorting by increasing distance. Taking the modulo at every step. These are small things, but getting any one of them wrong means a wrong answer. Spaced repetition turns these details into muscle memory so you write them correctly without thinking.

Related posts

• Network Delay Time - The foundational Dijkstra problem
• Cheapest Flights Within K Stops - Another shortest-path variation with constraints
• Course Schedule - Topological ordering on directed graphs

CodeBricks breaks Number of Restricted Paths into its Dijkstra and DAG-path-counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a shortest-path-plus-DP problem shows up in your interview, you do not hesitate. You just write it.