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 <= 105The key idea is to transform the problem using shortest path distances. First, run Dijkstra’s algorithm from node n to compute the minimum distance from every node to the last node. These distances help define a restricted path: a path where the distance to node n strictly decreases at each step.
Once distances are known, the graph can be treated like a directed structure where edges only go from nodes with larger distance values to smaller ones. From here, we count the number of ways to reach node n from node 1 using Dynamic Programming with memoized DFS or by processing nodes in distance order (similar to a topological idea).
The DFS sums valid paths from neighbors that have a smaller shortest-path distance. Memoization avoids recomputation, making the solution efficient even for larger graphs. Overall complexity is dominated by Dijkstra’s shortest path computation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dijkstra + DFS/DP Counting | O((V + E) log V) | O(V + E) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Run a Dijkstra from node numbered n to compute distance from the last node.
Consider all edges [u, v] one by one and direct them such that distance of u to n > distance of v to n. If both u and v are at the same distance from n, discard this edge.
Now this problem reduces to computing the number of paths from 1 to n in a DAG, a standard DP problem.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Running Dijkstra from node n directly gives the shortest distance from every node to the destination. This makes it easy to enforce the restricted path rule, which requires distances to strictly decrease along the path.
Yes, problems combining shortest paths with dynamic programming or graph traversal are common in FAANG-style interviews. This question tests understanding of Dijkstra’s algorithm, graph direction transformation, and memoized DFS.
A priority queue (min-heap) is used for Dijkstra’s algorithm to efficiently compute shortest distances. An adjacency list represents the graph, and a memoization array or map helps store intermediate path counts during DFS.
The optimal approach first computes the shortest distance from every node to node n using Dijkstra’s algorithm. Then it counts restricted paths from node 1 using DFS with memoization or DP, only moving to neighbors with strictly smaller distance values.