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.
To solve this problem, we first use Dijkstra's Algorithm to find the shortest path from the last node (node n) to every other node in the graph. This allows us to compute distanceToLastNode for each node. Then, using dynamic programming, we count the number of restricted paths from node 1 to node n. A restricted path is one where for each consecutive pair of nodes [u, v] in the path, distanceToLastNode(u) > distanceToLastNode(v).
In the dynamic programming function, we'll use memoization to store the number of restricted paths from a given node to the last node, which prevents redundant calculations and optimizes the solution.
This solution starts by constructing the graph and then utilizes Dijkstra's algorithm to find the shortest path from the last node to all others, recorded in the dist array. In the second part, it uses a DFS approach to count paths while checking the restricted path condition, storing results in memo to avoid repeating work.
Python
JavaScript
Time Complexity: O((n + m) log n), where n is the number of nodes and m is the number of edges, due to Dijkstra's algorithm and DFS with memoization.
Space Complexity: O(n + m) for the graph representation and distance/memoization arrays.
Another approach involves using the graph's nature and transforming it into a Directed Acyclic Graph (DAG) by considering only edges where the distanceToLastNode property holds. With a DAG, we can perform a topological sort to determine a valid order of nodes, then use dynamic programming to calculate restricted paths from node 1 to node n.
This C++ solution leverages sorting nodes based on their distances from the last node to create a topologically sorted order. Using this order, we can process each node in decreasing distance order to calculate the number of restricted paths. The function dfs is a recursive DP implementation storing results to avoid recomputation.
Time Complexity: O((n + m) log n), due to sorting nodes and typical graph processing operations.
Space Complexity: O(n + m) for graph representation and additional data structures.
| Approach | Complexity |
|---|---|
| Approach 1: Modified Dijkstra's Algorithm with Memoization | Time Complexity: O((n + m) log n), where n is the number of nodes and m is the number of edges, due to Dijkstra's algorithm and DFS with memoization. |
| Approach 2: DAG Shortest Path with Topological Sorting | Time Complexity: O((n + m) log n), due to sorting nodes and typical graph processing operations. |
| Default Approach | — |
| 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 |
5699. Number of Restricted Paths From First to Last Node • Fraz • 4,742 views views
Watch 9 more video solutions →Practice Number of Restricted Paths From First to Last Node with our built-in code editor and test cases.
Practice on FleetCode