Number of Restricted Paths From First to Last Node
MedPrompt
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:
distanceToLastNode value in blue. Example 2:
distanceToLastNode value in blue.
Constraints:
1 <= n <= 2 * 104n - 1 <= edges.length <= 4 * 104edges[i].length == 31 <= ui, vi <= nui != vi1 <= weighti <= 105- There is at most one edge between any two nodes.
- There is at least one path between any two nodes.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- First, compute the shortest distance from node
nto all other nodes using Dijkstra's algorithm. Store these in adistarray. * Define a recursive DFS functiondfs(u, currentPath, visited)to explore paths from nodeu. * In the DFS, ifuis the destinationn, check if thecurrentPathis a restricted path by verifyingdist[path[i]] > dist[path[i+1]]for alli. If so, increment a global counter. * For each neighborvofu, ifvis not invisited, recursively calldfs(v, ...). * Start the search fromdfs(1, ...). * This approach is not practical and is presented for completeness.
Walkthrough
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.
Complexity
Time
O(E log N + N!)
Space
O(N + E + N!)
Trade-offs
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.
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.
Algorithm
- Compute the
distarray using Dijkstra's algorithm starting from noden. * Define a recursive functiondfs(u)that calculates the number of restricted paths fromuton. * The base case for the recursion isu == n, which returns 1. * For a nodeu, iterate through its neighborsv. Ifdist[u] > dist[v], add the result ofdfs(v)to the count foru. * The final answer isdfs(1).
Walkthrough
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; } }
Complexity
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.
Trade-offs
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.
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.
Algorithm
- Step 1: Shortest Paths: Build an adjacency list and run Dijkstra's algorithm starting from node
nto computedist[i] = distanceToLastNode(i)for alli. * Step 2: Memoized Path Counting: Create a memoization arraymemoinitialized to -1. * Define a recursive functiondfs(u): * Ifu == n, return 1. * Ifmemo[u]is not -1, returnmemo[u]. * Initializecount = 0. For each neighborvofuwheredist[u] > dist[v], adddfs(v)tocount. * Store the result inmemo[u]and return it. * Step 3: Final Answer: Calldfs(1)to get the total number of restricted paths.
Walkthrough
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]; } }
Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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)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 ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.