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.
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 ; } }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.