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 <= 105To solve this problem, we first use Dijkstra's Algorithm to find the shortest path from the last node (node n) to every other node in the graph. This allows us to compute distanceToLastNode for each node. Then, using dynamic programming, we count the number of restricted paths from node 1 to node n. A restricted path is one where for each consecutive pair of nodes [u, v] in the path, distanceToLastNode(u) > distanceToLastNode(v).
In the dynamic programming function, we'll use memoization to store the number of restricted paths from a given node to the last node, which prevents redundant calculations and optimizes the solution.
This solution starts by constructing the graph and then utilizes Dijkstra's algorithm to find the shortest path from the last node to all others, recorded in the dist array. In the second part, it uses a DFS approach to count paths while checking the restricted path condition, storing results in memo to avoid repeating work.
JavaScript
Time Complexity: O((n + m) log n), where n is the number of nodes and m is the number of edges, due to Dijkstra's algorithm and DFS with memoization.
Space Complexity: O(n + m) for the graph representation and distance/memoization arrays.
Another approach involves using the graph's nature and transforming it into a Directed Acyclic Graph (DAG) by considering only edges where the distanceToLastNode property holds. With a DAG, we can perform a topological sort to determine a valid order of nodes, then use dynamic programming to calculate restricted paths from node 1 to node n.
This C++ solution leverages sorting nodes based on their distances from the last node to create a topologically sorted order. Using this order, we can process each node in decreasing distance order to calculate the number of restricted paths. The function dfs is a recursive DP implementation storing results to avoid recomputation.
Java
Time Complexity: O((n + m) log n), due to sorting nodes and typical graph processing operations.
Space Complexity: O(n + m) for graph representation and additional data structures.
| Approach | Complexity |
|---|---|
| Approach 1: Modified Dijkstra's Algorithm with Memoization | Time Complexity: O((n + m) log n), where n is the number of nodes and m is the number of edges, due to Dijkstra's algorithm and DFS with memoization. |
| Approach 2: DAG Shortest Path with Topological Sorting | Time Complexity: O((n + m) log n), due to sorting nodes and typical graph processing operations. |
How to EASILY solve LeetCode problems • NeetCode • 427,716 views views
Watch 9 more video solutions →Practice Number of Restricted Paths From First to Last Node with our built-in code editor and test cases.
Practice on FleetCode