Watch 10 video solutions for Number of Restricted Paths From First to Last Node, a medium level problem involving Dynamic Programming, Graph, Topological Sort. This walkthrough by Fraz has 4,742 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [ui, vi, weighti] denotes that there is an edge between nodes ui and vi with weight equal to weighti.
A path from node start to node end is a sequence of nodes [z0, z1, z2, ..., zk] such that z0 = start and zk = end and there is an edge between zi and zi+1 where 0 <= i <= k-1.
The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(zi) > distanceToLastNode(zi+1) where 0 <= i <= k-1.
Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 109 + 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
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5
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: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 --> 3 --> 7.
Constraints:
1 <= n <= 2 * 104n - 1 <= edges.length <= 4 * 104edges[i].length == 31 <= ui, vi <= nui != vi1 <= weighti <= 105Problem Overview: You are given an undirected weighted graph with n nodes. A path from node 1 to node n is restricted if the shortest distance to node n strictly decreases at every step along the path. The task is to count how many such restricted paths exist, modulo 1e9 + 7.
Approach 1: Modified Dijkstra's Algorithm with Memoization (O(E log V) time, O(V + E) space)
The key observation: whether a step is valid depends on the shortest distance from each node to node n. Compute these distances first using shortest path logic. Run Dijkstra's algorithm starting from node n so you get dist[x] = shortest distance from x to n. Once distances are known, a restricted path simply means moving from a node to a neighbor with a strictly smaller distance value.
After this preprocessing, the graph effectively becomes a directed acyclic structure if you only keep edges that go from larger dist to smaller dist. Use DFS from node 1 and count valid paths recursively. Memoization stores the number of ways to reach n from each node so each state is computed once. Every DFS step iterates through neighbors and only continues if dist[next] < dist[current]. This combines dynamic programming with graph traversal to avoid recomputation.
Approach 2: DAG Shortest Path with Topological Sorting (O(E log V + V log V) time, O(V + E) space)
After computing shortest distances to node n using Dijkstra, orient every edge from the node with larger distance to the node with smaller distance. Because distances strictly decrease, the resulting graph forms a DAG. Counting restricted paths becomes a classic DP-on-DAG problem.
Sort nodes by increasing dist value (which acts as a topological order). Initialize dp[n] = 1 because there is exactly one way to stay at node n. Traverse nodes in sorted order and propagate counts to neighbors with larger distance values in reverse direction. Each transition adds dp[next] into the current node’s count while applying modulo arithmetic. This approach removes recursion and replaces it with iterative dynamic programming over the DAG structure.
Recommended for interviews: The Dijkstra + memoized DFS approach is the one most candidates implement. It shows understanding of graph traversal, shortest paths, and DP with caching. The DAG + topological DP approach demonstrates deeper insight into how the distance constraint implicitly creates a DAG and is often discussed as an optimization or alternative explanation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Modified Dijkstra + Memoized DFS | O(E log V) | O(V + E) | General case; easiest to implement in interviews |
| DAG DP with Topological Ordering | O(E log V + V log V) | O(V + E) | When you want an iterative DP solution without recursion |