Number of Restricted Paths From First to Last Node

MEDIUM

Description

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] = [u_i, v_i, weight_i] denotes that there is an edge between nodes u_i and v_i with weight equal to weight_i.

A path from node start to node end is a sequence of nodes [z₀, z₁,z₂, ..., z_k] such that z₀= start and z_k = end and there is an edge between z_i and z_i+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(z_i) > distanceToLastNode(z_i+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 10⁹ + 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 * 10⁴
n - 1 <= edges.length <= 4 * 10⁴
edges[i].length == 3
1 <= u_i, v_i <= n
u_i!= v_i
1 <= weight_i <= 10⁵
There is at most one edge between any two nodes.
There is at least one path between any two nodes.

Approaches

Checkout 3 different approaches to solve Number of Restricted Paths From First to Last Node. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: O(E log N + N!)Space Complexity: O(N + E + N!)

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Number of Restricted Paths From First to Last Node. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Number of Restricted Paths From First to Last Node

Algorithms:

Topological SortShortest Path

Patterns:

Dynamic Programming

Data Structures:

Heap (Priority Queue)Graph