Number of Restricted Paths From First to Last Node — Hard Problem & Solution

An undirected weighted connected graph has n nodes numbered 1 … n, with edges[i] = [u, v, weight].

Difficulty: Hard
Topics: Dynamic Programming, Heap, Graph, Shortest Path
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An undirected weighted connected graph has n nodes numbered 1 … n, with edges[i] = [u, v, weight]. Let distanceToLastNode(x) be the shortest distance from node x to node n.

A path z1 → z2 → … → zk is restricted when distanceToLastNode(z1) > distanceToLastNode(z2) > … > distanceToLastNode(zk). Return the number of restricted paths from node 1 to node n, modulo 10^9 + 7.

Example 1

Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output: 3

Example 2

Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output: 1
Explanation: Only `1 → 3 → 7` keeps the distances strictly decreasing.

Example 3

Input: n = 2, edges = [[1,2,5]]
Output: 1

Constraints

1 <= n <= 1000
n - 1 <= edges.length <= 2 * 10^4
edges[i].length == 3
1 <= u, v <= n
u != v
1 <= weight <= 1000
There is at most one edge between any two nodes.
There is at least one path between every pair of nodes.

How to solve Number of Restricted Paths From First to Last Node

Run Dijkstra from node n to get every node's distance, then count paths with ways[u] = Σ ways[v] over neighbours v that are strictly closer to n. Processing nodes in increasing distance makes every ways[v] final before it is used.

Approach

Dijkstra from node n gives dist[x] for all x.
Set ways[n] = 1 — the empty path ending at n.
Sort the nodes by dist ascending and sweep them.
For node u, sum ways[v] over neighbours with dist[v] < dist[u], modulo 10^9 + 7.
Return ways[1].

Why it works

The strict inequality is what makes counting possible at all: it forbids cycles, turning the allowed moves into a DAG whose topological order is exactly "sorted by distance". Ties in dist never create an edge, since a move needs a strict drop, so equal-distance nodes can be processed in any relative order.

Complexity

Time — O(n² + m) with a plain Dijkstra, or O(m log n) with a heap
Space — O(n + m)

Pitfalls

Dijkstra must run from node n, not from node 1.
ways[n] = 1 is the base case; forgetting it makes every answer 0.
Take the modulus while summing, not only at the end.

Reference solution

Python

from typing import List
import heapq

def countRestrictedPaths(n: int, edges: List[List[int]]) -> int:
    MOD = 1000000007
    adj = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    BIG = float('inf')
    dist = [BIG] * (n + 1)
    dist[n] = 0
    heap = [(0, n)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    ways = [0] * (n + 1)
    ways[n] = 1
    for u in sorted(range(1, n + 1), key=lambda x: dist[x]):
        if u == n:
            continue
        total = 0
        for v, _ in adj[u]:
            if dist[v] < dist[u]:
                total = (total + ways[v]) % MOD
        ways[u] = total
    return ways[1]

JavaScript

var countRestrictedPaths = function(n, edges) {
    var MOD = 1000000007, BIG = 1000000000, i, k;
    var adj = [];
    for (i = 0; i <= n; i++) adj.push([]);
    for (i = 0; i < edges.length; i++) {
        adj[edges[i][0]].push([edges[i][1], edges[i][2]]);
        adj[edges[i][1]].push([edges[i][0], edges[i][2]]);
    }
    var dist = [], done = [];
    for (i = 0; i <= n; i++) { dist.push(BIG); done.push(false); }
    dist[n] = 0;
    for (var it = 0; it < n; it++) {
        var u = -1, best = BIG;
        for (i = 1; i <= n; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = true;
        for (k = 0; k < adj[u].length; k++) {
            var v = adj[u][k][0], w = adj[u][k][1];
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
    var order = [];
    for (i = 1; i <= n; i++) order.push(i);
    order.sort(function(a, b) { return dist[a] - dist[b]; });
    var ways = [];
    for (i = 0; i <= n; i++) ways.push(0);
    ways[n] = 1;
    for (i = 0; i < order.length; i++) {
        var node = order[i];
        if (node === n) continue;
        var total = 0;
        for (k = 0; k < adj[node].length; k++) {
            var nb = adj[node][k][0];
            if (dist[nb] < dist[node]) total = (total + ways[nb]) % MOD;
        }
        ways[node] = total;
    }
    return ways[1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 195 dynamic programming problems · the whole catalogue