#1786

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Number of Restricted Paths From First to Last Node

Solve the problem of finding the number of restricted paths in a weighted undirected graph, leveraging graph algorithms and dynamic programming.

dynamic programming graph topological sort heap priority queue shortest path

Problem Statement

You are given a weighted undirected connected graph with n nodes numbered from 1 to n. Each edge is described by a triplet [ui, vi, weighti], meaning there is an edge between nodes ui and vi with the specified weight weighti. The goal is to calculate the number of restricted paths from node 1 to node n.

A restricted path is defined as a path from node 1 to node n such that the path’s weights are strictly decreasing in the direction of traversal. You need to return the number of such restricted paths modulo 10^9 + 7. Given the constraints, a brute-force approach will not suffice, and leveraging algorithms like Dijkstra and dynamic programming is crucial for an optimal solution.

Examples

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

Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:

1 --> 2 --> 5
1 --> 2 --> 3 --> 5
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

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.

Solution Approach

Use Dijkstra's Algorithm in Reverse

To solve the problem efficiently, start by running Dijkstra's algorithm from node n to compute the shortest distance to all nodes in reverse. This helps in determining the distance of each node from node n, allowing us to efficiently decide whether a node can be part of a restricted path.

Topological Sort and Dynamic Programming

After calculating the shortest distances from node n, you can perform a topological sort of the nodes based on these distances. This enables dynamic programming where each node’s restricted path count is computed by accumulating the restricted paths from its neighbors that satisfy the condition of strictly decreasing path weights.

Modulo Operation for Large Numbers

Since the number of restricted paths could be large, make sure to apply the modulo 10^9 + 7 at each step of dynamic programming to prevent overflow and ensure that the final result is within the required bounds.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach, but typically, using Dijkstra’s algorithm with a priority queue and dynamic programming results in a time complexity of O(E log V), where E is the number of edges and V is the number of nodes. The space complexity is O(V + E), accounting for the storage of the graph, distances, and dynamic programming results.

What Interviewers Usually Probe

Ensure the candidate is comfortable with both graph traversal techniques and dynamic programming.
Look for a clear understanding of why Dijkstra’s algorithm is applied in reverse for this problem.
The candidate should demonstrate knowledge of how to handle large numbers with modular arithmetic.

Common Pitfalls or Variants

Common pitfalls

Not using Dijkstra's algorithm in reverse order, which leads to incorrect path calculations.
Forgetting to apply the modulo operation when the number of paths becomes large.
Improper handling of the dynamic programming state, which may result in an incorrect count of restricted paths.

Follow-up variants

Consider variations of the problem where the graph is directed, requiring different approaches to track restricted paths.
Introduce additional constraints such as path length limits or restrictions on the number of hops between nodes.
Explore the problem by relaxing the condition on restricted paths, allowing non-decreasing path weights.

FAQ

What is the main algorithm used in the 'Number of Restricted Paths From First to Last Node' problem?

The main algorithm used is Dijkstra's algorithm in reverse to compute the shortest path distances from the last node to all other nodes in the graph.

How does dynamic programming contribute to solving this problem?

Dynamic programming helps in calculating the number of restricted paths from node 1 to node n by accumulating results from neighboring nodes in topological order.

Why is a topological sort important in this problem?

Topological sort is crucial because it ensures that nodes are processed in the correct order, respecting the strict decreasing weight condition for restricted paths.

What is the time complexity of solving this problem?

The time complexity is O(E log V), where E is the number of edges and V is the number of nodes, due to the use of Dijkstra’s algorithm with a priority queue.

How does the modulo operation affect the final result?

The modulo operation ensures that the final number of restricted paths is within the bounds of 10^9 + 7, preventing overflow and maintaining computational limits.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

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)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

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)

Continue Practicing

#1976 number of ways to arrive at destination #3620 network recovery pathways #787 cheapest flights within k stops