# Number of Restricted Paths From First to Last Node
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node)
Canonical: https://scaleengineer.com/dsa/problems/number-of-restricted-paths-from-first-to-last-node
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Heap (Priority Queue), Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/number-of-restricted-paths-from-first-to-last-node/image0.png) 

**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:**

![](https://assets.glich.co/dsa/number-of-restricted-paths-from-first-to-last-node/image1.png) 

**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 * 104`
* `n - 1 <= edges.length <= 4 * 104`
* `edges[i].length == 3`
* `1 <= ui, vi <= n`
* `ui != vi`
* `1 <= weighti <= 105`
* There is at most one edge between any two nodes.
* There is at least one path between any two nodes.

# Approaches
## Brute-Force Path Enumeration
This approach first calculates the shortest distance from every node to node `n` using Dijkstra's algorithm. Then, it attempts to find all possible simple paths (paths without repeated nodes) from node 1 to node `n` using a Depth-First Search (DFS). For each path found, it checks if it satisfies the 'restricted path' condition: `distanceToLastNode(z_i) > distanceToLastNode(z_{i+1})` for all consecutive nodes in the path. If a path is restricted, a counter is incremented.
**Time:** O(E log N + N!) · **Space:** O(N + E + N!)
**Pros:** Conceptually simple to understand as it directly follows the problem definition.
**Cons:** Extremely inefficient due to the enumeration of all simple paths.; The number of paths can be factorial in the number of nodes, making it infeasible for the given constraints.; Will result in a 'Time Limit Exceeded' error on any non-trivial test case.
### Explanation
The algorithm proceeds in three main steps: 1. **Compute Shortest Distances:** Run Dijkstra's algorithm starting from node `n` to populate an array `dist`, where `dist[i]` stores the shortest distance from node `n` to node `i`. 2. **Find All Paths via DFS:** Implement a recursive DFS function, say `findAllPaths(u, path, visited)`. The function takes the current node `u`, the path traversed so far, and a set of visited nodes to avoid cycles. The base case is when `u == n`, at which point a path from 1 to `n` is found. This path is then validated to see if it's restricted by iterating through it and checking the distance condition. If it is, a global counter is incremented. In the recursive step, the function iterates through all neighbors `v` of `u`. If `v` has not been visited, a recursive call is made. 3. **Initial Call:** Start the process by calling `findAllPaths(1, [1], {1})`. This method is fundamentally flawed for this problem's constraints because the number of simple paths in a graph can be astronomically large.
### Algorithm
*   First, compute the shortest distance from node `n` to all other nodes using Dijkstra's algorithm. Store these in a `dist` array. *   Define a recursive DFS function `dfs(u, currentPath, visited)` to explore paths from node `u`. *   In the DFS, if `u` is the destination `n`, check if the `currentPath` is a restricted path by verifying `dist[path[i]] > dist[path[i+1]]` for all `i`. If so, increment a global counter. *   For each neighbor `v` of `u`, if `v` is not in `visited`, recursively call `dfs(v, ...)`. *   Start the search from `dfs(1, ...)`. *   This approach is not practical and is presented for completeness.

## Recursive Backtracking without Memoization
This approach improves upon the brute-force method by integrating the 'restricted path' condition directly into the search. After computing the shortest distances from all nodes to node `n` (the `dist` array), it performs a Depth-First Search (DFS) from node 1. The key difference is that the DFS only explores an edge from a node `u` to a neighbor `v` if `dist[u] > dist[v]`. This pruning step ensures that any path found is guaranteed to be a restricted path. However, without memoization, this approach still suffers from re-computing the number of paths from the same node multiple times.
**Time:** O(E log N + k), where k is the number of restricted paths. In the worst case, k can be exponential. · **Space:** O(N + E) for the graph, Dijkstra's data structures, and the recursion stack.
**Pros:** More efficient than full brute-force by pruning the search space.; Correctly identifies the problem as path counting on a DAG.
**Cons:** Still inefficient due to re-computation of subproblems.; The number of recursive calls can be exponential in `N`, leading to a 'Time Limit Exceeded' error for many test cases.
### Explanation
The algorithm is as follows: 1. **Compute Shortest Distances:** As in the previous approach, run Dijkstra's algorithm from the destination node `n` to find `distanceToLastNode` for every node. 2. **Recursive Counting:** Define a recursive function, `countPaths(u)`, which returns the number of restricted paths from `u` to `n`. *   The base case is `if (u == n)`, return 1. *   Initialize a counter `totalPaths = 0`. *   For each neighbor `v` of `u`, if `dist[u] > dist[v]`, recursively call `countPaths(v)` and add the result to `totalPaths` (modulo `10^9 + 7`). *   Return `totalPaths`. 3. **Initial Call:** The final answer is the result of `countPaths(1)`. The condition `dist[u] > dist[v]` implicitly defines a Directed Acyclic Graph (DAG). This method essentially counts all paths from 1 to `n` in this DAG, but its recursive nature without memoization leads to redundant computations for nodes that can be reached via multiple paths. ```java // Note: This approach is for illustration and will also time out on many cases. class Solution { long[] dist; List<List<int[]>> adj; int MOD = 1_000_000_007; int N; public int countRestrictedPaths(int n, int[][] edges) { this.N = n; adj = new ArrayList<>(); for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(new int[]{edge[1], edge[2]}); adj.get(edge[1]).add(new int[]{edge[0], edge[2]}); } dist = new long[n + 1]; Arrays.fill(dist, Long.MAX_VALUE); dist[n] = 0; PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0])); pq.offer(new long[]{0, n}); while (!pq.isEmpty()) { long[] curr = pq.poll(); long d = curr[0]; int u = (int) curr[1]; if (d > dist[u]) continue; for (int[] neighbor : adj.get(u)) { int v = neighbor[0]; int weight = neighbor[1]; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.offer(new long[]{dist[v], v}); } } } return dfs(1); } private int dfs(int u) { if (u == N) { return 1; } long count = 0; for (int[] neighbor : adj.get(u)) { int v = neighbor[0]; if (dist[u] > dist[v]) { count = (count + dfs(v)) % MOD; } } return (int) count; } } ```
### Algorithm
*   Compute the `dist` array using Dijkstra's algorithm starting from node `n`. *   Define a recursive function `dfs(u)` that calculates the number of restricted paths from `u` to `n`. *   The base case for the recursion is `u == n`, which returns 1. *   For a node `u`, iterate through its neighbors `v`. If `dist[u] > dist[v]`, add the result of `dfs(v)` to the count for `u`. *   The final answer is `dfs(1)`.

## Dijkstra's Algorithm with Memoized DFS
This is the optimal and efficient approach. It combines Dijkstra's algorithm with dynamic programming (using memoization). First, Dijkstra's algorithm is used to find the shortest distance from node `n` to all other nodes. This information is then used to guide a memoized Depth-First Search (DFS) to count the number of restricted paths. The memoization prevents re-calculating the number of paths from a node that has already been visited, drastically reducing the computation time.
**Time:** O(E log N). Dijkstra's algorithm takes O(E log N). The memoized DFS visits each node and edge once, taking O(N + E). The total is dominated by Dijkstra's. · **Space:** O(N + E). This is for the adjacency list, `dist` array, `memo` array, and the recursion stack.
**Pros:** Highly efficient and optimal for the given constraints.; Correctly solves the problem by combining two standard, powerful algorithms: Dijkstra's for shortest paths and DP/memoization for path counting on a DAG.
**Cons:** Slightly more complex to implement than naive approaches due to the combination of algorithms.
### Explanation
The algorithm consists of two main phases: 1. **Compute Shortest Distances:** Run Dijkstra's algorithm starting from node `n` to compute the `dist` array, where `dist[i]` is the shortest distance from node `n` to node `i`. This is a standard single-source shortest path calculation on a graph with non-negative weights. 2. **Count Paths with Memoized DFS:** *   Create a memoization array, `memo`, of size `n+1`, and initialize all its values to -1 to indicate that the number of paths from any node has not been computed yet. *   Implement a recursive function `dfs(u)` that calculates the number of restricted paths from node `u` to `n`. *   **Base Case:** If `u == n`, we've reached the destination. There is one path (the trivial path), so return 1. *   **Memoization Check:** If `memo[u]` is not -1, it means we have already computed the result for node `u`. Return the stored value `memo[u]` immediately. *   **Recursive Step:** Initialize a counter `count = 0`. Iterate through all neighbors `v` of `u`. If `dist[u] > dist[v]`, it's a valid move in a restricted path. Recursively call `dfs(v)` and add the result to `count`. Perform addition modulo `10^9 + 7`. *   **Store Result:** Before returning, store the computed `count` in `memo[u]` so it can be reused. 3. **Initial Call:** The final answer is obtained by calling `dfs(1)`. ```java import java.util.*; class Solution { private static final int MOD = 1_000_000_007; private List<List<int[]>> adj; private long[] dist; private int[] memo; private int N; public int countRestrictedPaths(int n, int[][] edges) { this.N = n; adj = new ArrayList<>(); for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(new int[]{edge[1], edge[2]}); adj.get(edge[1]).add(new int[]{edge[0], edge[2]}); } dist = new long[n + 1]; Arrays.fill(dist, Long.MAX_VALUE); dist[n] = 0; PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0])); pq.offer(new long[]{0, n}); while (!pq.isEmpty()) { long[] current = pq.poll(); long d = current[0]; int u = (int) current[1]; if (d > dist[u]) { continue; } for (int[] neighbor : adj.get(u)) { int v = neighbor[0]; int weight = neighbor[1]; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.offer(new long[]{dist[v], v}); } } } memo = new int[n + 1]; Arrays.fill(memo, -1); return dfs(1); } private int dfs(int u) { if (u == N) { return 1; } if (memo[u] != -1) { return memo[u]; } long count = 0; for (int[] neighbor : adj.get(u)) { int v = neighbor[0]; if (dist[u] > dist[v]) { count = (count + dfs(v)) % MOD; } } memo[u] = (int) count; return memo[u]; } } ```
### Algorithm
*   **Step 1: Shortest Paths:** Build an adjacency list and run Dijkstra's algorithm starting from node `n` to compute `dist[i] = distanceToLastNode(i)` for all `i`. *   **Step 2: Memoized Path Counting:** Create a memoization array `memo` initialized to -1. *   Define a recursive function `dfs(u)`: *   If `u == n`, return 1. *   If `memo[u]` is not -1, return `memo[u]`. *   Initialize `count = 0`. For each neighbor `v` of `u` where `dist[u] > dist[v]`, add `dfs(v)` to `count`. *   Store the result in `memo[u]` and return it. *   **Step 3: Final Answer:** Call `dfs(1)` to get the total number of restricted paths.

# Solutions
### Java

```java
class Solution { private static final int INF = Integer . MAX_VALUE ; private static final int MOD = ( int ) 1 e9 + 7 ; private List < int []>[] g ; private int [] dist ; private int [] f ; private int n ; public int countRestrictedPaths ( int n , int [][] edges ) { this . n = n ; g = new List [ n + 1 ]; for ( int i = 0 ; i < g . length ; ++ i ) { g [ i ] = new ArrayList <>(); } for ( int [] e : edges ) { int u = e [ 0 ], v = e [ 1 ], w = e [ 2 ]; g [ u ]. add ( new int [] { v , w }); g [ v ]. add ( new int [] { u , w }); } PriorityQueue < int []> q = new PriorityQueue <>(( a , b ) -> a [ 0 ] - b [ 0 ]); q . offer ( new int [] { 0 , n }); dist = new int [ n + 1 ]; f = new int [ n + 1 ]; Arrays . fill ( dist , INF ); Arrays . fill ( f , - 1 ); dist [ n ] = 0 ; while (! q . isEmpty ()) { int [] p = q . poll (); int u = p [ 1 ]; for ( int [] ne : g [ u ]) { int v = ne [ 0 ], w = ne [ 1 ]; if ( dist [ v ] > dist [ u ] + w ) { dist [ v ] = dist [ u ] + w ; q . offer ( new int [] { dist [ v ], v }); } } } return dfs ( 1 ); } private int dfs ( int i ) { if ( f [ i ] != - 1 ) { return f [ i ]; } if ( i == n ) { return 1 ; } int ans = 0 ; for ( int [] ne : g [ i ]) { int j = ne [ 0 ]; if ( dist [ i ] > dist [ j ]) { ans = ( ans + dfs ( j )) % MOD ; } } f [ i ] = ans ; return ans ; } }
```

### Python

```python
class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int: @ cache def dfs(i): if i == n: return 1 ans = 0 for j, _ in g[i]: if dist[i] > dist[j]: ans = (ans + dfs(j)) % mod return ans g = defaultdict(list) for u, v, w in edges: g[u]. append((v, w)) g[v]. append((u, w)) q = [(0, n)] dist = [inf] * (n + 1) dist[n] = 0 mod = 10 ** 9 + 7 while q: _, u = heappop(q) for v, w in g[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w heappush(q, (dist[v], v)) return dfs(1)

```

### CPP

```cpp
using pii = pair < int , int > ; class Solution { public: const int inf = INT_MAX ; const int mod = 1e9 + 7 ; vector < vector < pii >> g ; vector < int > dist ; vector < int > f ; int n ; int countRestrictedPaths ( int n , vector < vector < int >>& edges ) { this -> n = n ; g . resize ( n + 1 ); dist . assign ( n + 1 , inf ); f . assign ( n + 1 , - 1 ); dist [ n ] = 0 ; for ( auto & e : edges ) { int u = e [ 0 ], v = e [ 1 ], w = e [ 2 ]; g [ u ]. emplace_back ( v , w ); g [ v ]. emplace_back ( u , w ); } priority_queue < pii , vector < pii > , greater < pii >> q ; q . emplace ( 0 , n ); while ( ! q . empty ()) { auto [ _ , u ] = q . top (); q . pop (); for ( auto [ v , w ] : g [ u ]) { if ( dist [ v ] > dist [ u ] + w ) { dist [ v ] = dist [ u ] + w ; q . emplace ( dist [ v ], v ); } } } return dfs ( 1 ); } int dfs ( int i ) { if ( f [ i ] != - 1 ) return f [ i ]; if ( i == n ) return 1 ; int ans = 0 ; for ( auto [ j , _ ] : g [ i ]) { if ( dist [ i ] > dist [ j ]) { ans = ( ans + dfs ( j )) % mod ; } } f [ i ] = ans ; return ans ; } };
```