1786. Number of Restricted Paths From First to Last Node

MediumGraphTopological SortDynamic ProgrammingShortest PathHeap (Priority Queue)
Leetcode Link

Problem Description

In this problem, we're dealing with an undirected, weighted, and connected graph consisting of n nodes labeled from 1 to n. An array edges describes the connections between the nodes, where each connection is an array [u_i, v_i, weight_i] representing an edge between nodes u_i and v_i with a weight weight_i.

The goal is to find the number of "restricted paths" from node 1 to node n. A restricted path is defined as one where the shortest distance from any node z_i on the path to node n is greater than the distance from the next node z_i+1 on the path to node n. This means that as you travel the path from 1 to n, the distance to the last node n is strictly decreasing at every step of the way.

The task is to return the total number of such paths modulo 10^9 + 7, to keep the answer within integer range limits.

Intuition

The solution leverages Dynamic Programming (DP) and a Depth-First Search (DFS) strategy to count the number of restricted paths.

The key ideas behind the solution are as follows:

  1. To know whether a path is "restrictive", we need to compare distances to node n. So, we must first compute the shortest distance from every node to node n. This is done using Dijkstra's algorithm.
  2. Once we have the shortest distances, we perform DFS starting from node 1. At each node, we only continue the search to adjacent nodes that have a shorter distance to node n than the current node, ensuring the "restrictive" property.
  3. We cache results to avoid recomputation—this is where DP comes in. If we've already computed the number of restricted paths from a given node to n, we use the cached value instead of recalculating it.
  4. The final result is obtained once the DFS is complete, and we consider the modulo 10^9 + 7 at each step to manage the potential large number of paths.

By structuring the problem this way, we can efficiently determine the number of restricted paths from node 1 to node n by making sure each move brings us closer to n in terms of the shortest path distance, thereby satisfying the conditions for a path to be "restricted".

Learn more about Graph, Topological Sort, Dynamic Programming, Shortest Path and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which of the following uses divide and conquer strategy?

Solution Approach

The implementation employs both Dijkstra's algorithm for finding shortest paths and a depth-first search (DFS) combined with dynamic programming for counting the number of restricted paths. Below is a step-by-step explanation of how the solution works:

  1. Dijkstra's Algorithm with Min-Heap:

    • We first initialize a graph g as a default dictionary of lists, where each node points to a list of tuples, each representing an adjacent node and the weight of the edge connecting them.
    • A priority queue (min-heap) q is used to keep track of the nodes during the execution of Dijkstra's algorithm, which is initialized with a tuple (0, n) indicating the distance to the last node n is 0.
    • An array dist of size n + 1 is created to store the shortest distance to node n for each node, initialized to infinity (inf), except dist[n] which is 0.
    • The Dijkstra's algorithm iterates while the min-heap q is not empty. It pops the node u with the smallest distance estimate, and for each adjacent node v with a weight w, it relaxes the edge by checking if dist[v] can be decreased by taking the edge u-v. If yes, update dist[v] and push it back on the min-heap with the updated distance.

  2. Depth-First Search with Dynamic Programming:

    • A recursive function dfs is defined with memoization (cache decorator) to remember the number of restricted paths from any node to node n. This memoization ensures we don't recompute paths for a node that has been already visited.
    • The dfs function searches each adjacent node j for the current node i. If dist[i] > dist[j], meaning that moving to node j from i gets us closer to node n (restricted path condition), we recursively call dfs(j) to count paths from j to n.
    • Each result is taken modulo 10^9 + 7 to prevent integer overflow and adhere to the problem's requirements to return the result modulo 10^9 + 7.
    • The dfs terminates when it reaches node n, returning 1 as there is exactly one restricted path from n to n.

  3. Execution and Return Statement:

    • After setting up the graph and computing the shortest distances using Dijkstra's algorithm, the dfs function is called starting from node 1.
    • The final count of the restricted paths from node 1 to node n is returned as the solution to the problem.

In conclusion, this approach combines graph algorithms with dynamic programming to solve a complex problem by breaking it down into manageable parts: finding the shortest path using Dijkstra and then using a restricted DFS to count the paths, using dynamic programming to optimize and prevent unnecessary recalculations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Let's make this practical with a small graph. Suppose our graph consists of 5 nodes, and we're given the following edges:

1edges = [[1, 2, 3], [1, 3, 5], [2, 4, 1], [3, 4, 1], [4, 5, 1]]

Here's a step-by-step walkthrough according to our solution approach:

  1. Initializing Graph and Shortest Distances:

    • We start by constructing our graph g from the edges, where for instance g[1] would give us [(2, 3), (3, 5)] indicating there are edges from node 1 to node 2 with a weight of 3 and to node 3 with a weight of 5.
    • Our priority queue (min-heap) q will be initialized with (0, 5) since we are considering the shortest path to node 5.
    • The dist array is initialized with Infinity values except dist[5] = 0.

  2. Dijkstra's Algorithm:

    • Using Dijkstra's algorithm, we pop the closest node from q, which initially is node 5. Since node 5 has no further connections ({5: []}), we continue.
    • Nodes 4, then 2, then 3, and finally 1 are popped in subsequent iterations. The distance array gets updated to reflect the shortest distance to node 5: dist = [inf, 5, 2, 4, 1, 0], implying the shortest path to reach node 5 from nodes 1, 2, 3, and 4 is 5, 2, 4, and 1, respectively.

  3. Depth-First Search:

    • Now we use the dfs function starting from node 1. Since dist[1] > dist[2], we can visit node 2. From 2, we can go to 4 since dist[2] > dist[4].
    • Now at node 4, we can directly go to 5 as dist[4] > dist[5]. This is a valid restricted path: 1 -> 2 -> 4 -> 5.
    • Backtracking to node 2, there are no more nodes to visit following the restricted path conditions, so we go back to node 1.
    • From node 1, we also have a direct edge to node 3. Since dist[1] > dist[3], we can visit node 3. Node 3 can go to node 4 for the same reason, and from node 4 to node 5, finding another restricted path: 1 -> 3 -> 4 -> 5.
    • No more paths exist from node 1 satisfying the restricted path conditions, so our dfs returns the count as 2.

  4. Execution and Return:

    • After executing the Dijkstra's algorithm to find the shortest paths to node 5 and running the depth-first search from node 1, we count the number of restricted paths that we've determined to be 2.
    • The final answer to be returned, given the constraint of the problem, is 2 % (10^9 + 7) which is simply 2.

This completed example illustrates how the solution approach navigates the problem to efficiently calculate the number of restricted paths from the first node to the last in a weighted, undirected graph.

Solution Implementation

1from collections import defaultdict
2from heapq import heappush, heappop
3from functools import cache
4from typing import List
5
6class Solution:
7    def count_restricted_paths(self, n: int, edges: List[List[int]]) -> int:
8        # A depth-first search function with memoization to count the number
9        # of restricted paths to node 'n', using a closure to access `dist` and `mod`.
10        @cache
11        def dfs(current_node):
12            # Base case: if the current node is the destination, there is one valid path.
13            if current_node == n:
14                return 1
15          
16            # Initialize the answer (number of restricted paths) from this node to zero.
17            answer = 0
18          
19            # Iterate over each adjacent node and weight.
20            for neighbor, _ in graph[current_node]:
21                # Only count paths from higher to lower `dist` values as restricted paths.
22                if dist[current_node] > dist[neighbor]:
23                    answer = (answer + dfs(neighbor)) % mod
24                  
25            # Return the total number of restricted paths from the current node.
26            return answer
27      
28        # Initializing the graph representation using a dictionary of lists.
29        graph = defaultdict(list)
30      
31        # Constructing the undirected weighted graph from edges.
32        for u, v, weight in edges:
33            graph[u].append((v, weight))
34            graph[v].append((u, weight))
35      
36        # Initialize a min-heap for finding the shortest paths.
37        min_heap = [(0, n)]
38      
39        # Set all distances to infinity initially and zero for the destination node 'n'.
40        dist = [float('inf')] * (n + 1)
41        dist[n] = 0
42      
43        # Define the modulo for output.
44        mod = 10**9 + 7
45      
46        # Implement Dijkstra's algorithm to find the shortest paths from node 'n' to all other nodes.
47        while min_heap:
48            _, current_node = heappop(min_heap)
49            for neighbor, weight in graph[current_node]:
50                # If a shorter path to neighbor is found, update its `dist` and push it onto the heap.
51                if dist[neighbor] > dist[current_node] + weight:
52                    dist[neighbor] = dist[current_node] + weight
53                    heappush(min_heap, (dist[neighbor], neighbor))
54      
55        # Call the dfs function to count restricted paths starting from node 1.
56        return dfs(1)
57
58# Note that the method name remains unchanged to conform with the original use-case.
59
1class Solution {
2    private static final int INFINITY = Integer.MAX_VALUE; // Represents unreachable distance
3    private static final int MODULUS = (int) 1e9 + 7; // Modulus value for number of paths
4    private List<int[]>[] graph; // Adjacency list representation of graph
5    private int[] distances; // Shortest distances from node n to other nodes
6    private int[] pathCounts; // Number of restricted paths to node n from other nodes
7    private int nodeCount; // Number of nodes in the graph
8
9    public int countRestrictedPaths(int n, int[][] edges) {
10        nodeCount = n;
11        graph = new List[n + 1];
12      
13        // Initialize the adjacency list
14        for (int i = 0; i < graph.length; ++i) {
15            graph[i] = new ArrayList<>();
16        }
17      
18        // Populate the graph with edges and corresponding weights
19        for (int[] edge : edges) {
20            int from = edge[0], to = edge[1], weight = edge[2];
21            graph[from].add(new int[] {to, weight});
22            graph[to].add(new int[] {from, weight});
23        }
24
25        // Min-heap to store nodes and their distances for Dijkstra's algorithm
26        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
27        priorityQueue.offer(new int[] {0, n}); // Starting from node n
28        distances = new int[n + 1];
29        pathCounts = new int[n + 1];
30      
31        // Initialize distances to infinity and path counts to -1
32        Arrays.fill(distances, INFINITY);
33        Arrays.fill(pathCounts, -1);
34      
35        // Distance from node n to itself is 0
36        distances[n] = 0;
37      
38        // Dijkstra's algorithm to find shortest paths from node n to all others
39        while (!priorityQueue.isEmpty()) {
40            int[] current = priorityQueue.poll();
41            int currentNode = current[1];
42
43            // Explore neighbors and update distances
44            for (int[] neighbor : graph[currentNode]) {
45                int nextNode = neighbor[0], weight = neighbor[1];
46                if (distances[nextNode] > distances[currentNode] + weight) {
47                    distances[nextNode] = distances[currentNode] + weight;
48                    priorityQueue.offer(new int[] {distances[nextNode], nextNode});
49                }
50            }
51        }
52      
53        // Start DFS from node 1 to calculate the restricted paths
54        return dfs(1);
55    }
56
57    private int dfs(int node) {
58        // If the number of paths has been computed previously, return it.
59        if (pathCounts[node] != -1) {
60            return pathCounts[node];
61        }
62      
63        // If we reached the destination node, there is one path.
64        if (node == nodeCount) {
65            return 1;
66        }
67
68        int countOfPaths = 0;
69      
70        // Explore all neighbours where the restricted path condition holds
71        for (int[] neighbor : graph[node]) {
72            int nextNode = neighbor[0];
73          
74            // If the neighbor is closer to n than the current node, continue the DFS
75            if (distances[node] > distances[nextNode]) {
76                countOfPaths = (countOfPaths + dfs(nextNode)) % MODULUS;
77            }
78        }
79
80        // Cache the results in pathCounts to avoid re-computation
81        pathCounts[node] = countOfPaths;
82        return countOfPaths;
83    }
84}
85
1#include <vector>
2#include <queue>
3#include <climits>
4
5using std::vector;
6using std::pair;
7using std::priority_queue;
8
9class Solution {
10public:
11    static const int INF = INT_MAX;       // Define infinity as the maximum value for an integer.
12    static const int MOD = 1e9 + 7;      // Define the modulo value for the problem.
13    vector<vector<pair<int, int>>> graph; // Adjacency list representation of the graph.
14    vector<int> distances;                // Vector to store distances from node n to other nodes.
15    vector<int> countWays;                // Vector to memoize number of ways to reach node n.
16    int nodes;                            // The number of nodes in the graph.
17
18    // Helper function to perform Dijkstra's algorithm to find shortest paths from node n.
19    void dijkstra(int source) {
20        priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> queue;
21        distances[source] = 0;
22        queue.emplace(0, source);
23
24        while (!queue.empty()) {
25            auto [currentDistance, currentNode] = queue.top();
26            queue.pop();
27            for (const auto& [nextNode, weight] : graph[currentNode]) {
28                if (distances[nextNode] > currentDistance + weight) {
29                    distances[nextNode] = currentDistance + weight;
30                    queue.emplace(distances[nextNode], nextNode);
31                }
32            }
33        }
34    }
35
36    // Depth-first search to count the number of restricted paths to node n.
37    int dfs(int currentNode) {
38        if (countWays[currentNode] != -1) {
39            return countWays[currentNode];
40        }
41        if (currentNode == nodes) {
42            return 1;
43        }
44        int answer = 0;
45        for (const auto& [nextNode, _] : graph[currentNode]) {
46            if (distances[currentNode] > distances[nextNode]) {
47                answer = (answer + dfs(nextNode)) % MOD;
48            }
49        }
50        countWays[currentNode] = answer;
51        return answer;
52    }
53
54    // Function to count the number of restricted paths from node 1 to node n.
55    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
56        nodes = n;
57        graph.resize(n + 1);
58        distances.assign(n + 1, INF);
59        countWays.assign(n + 1, -1);
60      
61        // Building the graph from the edge list.
62        for (const auto& edge : edges) {
63            int u = edge[0], v = edge[1], weight = edge[2];
64            graph[u].emplace_back(v, weight);
65            graph[v].emplace_back(u, weight);
66        }
67      
68        // Finding all shortest paths from node n.
69        dijkstra(n);
70      
71        // Initiating a DFS from node 1 to count all paths.
72        return dfs(1);
73    }
74};
75
1// Type representing a graph as an array of arrays where each element contains a pair of numbers.
2type Graph = Array<Array<[number, number]>>;
3
4// Constants representing infinity and the modulo value.
5const INF: number = Number.MAX_SAFE_INTEGER;
6const MOD: number = 1e9 + 7;
7
8// Global variables representing the graph, distances, and ways to count.
9let graph: Graph;
10let distances: number[];
11let countWays: number[];
12let nodes: number;
13
14// Function to perform Dijkstra's algorithm to find shortest paths from node n.
15function dijkstra(source: number): void {
16  let prioQueue: Array<[number, number]> = [];
17  distances[source] = 0;
18  prioQueue.push([0, source]);
19
20  // Custom sort to turn array into a min-heap based priority queue.
21  prioQueue.sort((a, b) => a[0] - b[0]);
22
23  while (prioQueue.length > 0) {
24    let [currentDistance, currentNode] = prioQueue.shift()!;
25
26    graph[currentNode].forEach(([nextNode, weight]) => {
27      if (distances[nextNode] > currentDistance + weight) {
28        distances[nextNode] = currentDistance + weight;
29        prioQueue.push([distances[nextNode], nextNode]);
30        // Maintain the queue as a min-heap on every insert.
31        prioQueue.sort((a, b) => a[0] - b[0]);
32      }
33    });
34  }
35}
36
37// Function to perform a Depth-First Search to count the number of restricted paths to node n.
38function dfs(currentNode: number): number {
39  if (countWays[currentNode] !== -1) {
40    return countWays[currentNode];
41  }
42  if (currentNode === nodes) {
43    return 1;
44  }
45  let answer: number = 0;
46  for (const [nextNode, ] of graph[currentNode]) {
47    if (distances[currentNode] > distances[nextNode]) {
48      answer = (answer + dfs(nextNode)) % MOD;
49    }
50  }
51  countWays[currentNode] = answer;
52  return answer;
53}
54
55// Function to count the number of restricted paths from node 1 to node n.
56function countRestrictedPaths(n: number, edges: Array<[number, number, number]>): number {
57  nodes = n;
58  graph = new Array(n + 1).fill(0).map(() => new Array<[number, number]>());
59  distances = new Array(n + 1).fill(INF);
60  countWays = new Array(n + 1).fill(-1);
61
62  // Build the graph from the edge list.
63  edges.forEach(([u, v, weight]) => {
64    graph[u].push([v, weight]);
65    graph[v].push([u, weight]);
66  });
67
68  // Find shortest paths from node n.
69  dijkstra(n);
70
71  // Start a DFS from node 1 to count all restricted paths.
72  return dfs(1);
73}
74
Not Sure What to Study? Take the 2-min Quiz

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Time and Space Complexity

Time Complexity

The given code consists of a Dijkstra's algorithm to find the shortest path from each node to the node n, followed by a depth-first search (DFS) with memoization to count the number of restricted paths.

  1. Dijkstra's Algorithm: The time complexity of Dijkstra's algorithm using a min heap (priority queue) is O(E + V log V), where E is the number of edges, and V is the number of vertices (or nodes) in the graph. In this case, each edge is processed once, and each node can be inserted into the priority queue at most once. Since this graph is undirected, each edge appears twice (once for each direction), leading to 2E operations, which simplifies back to O(E). Thus, the complexity is O(E + V log V) for building the dist array.

  2. Depth-First Search (DFS) with memoization: The DFS is called for each node starting from node 1 and ends at node n. Each function call may lead to further recursive calls. However, because of memoization and the condition if dist[i] > dist[j], each pair (i, j) is considered only once. The total number of recursive calls is bounded by the number of edges E, thus the time complexity for dfs is O(E).

Combining both parts, the overall time complexity is O(E + V log V + E), which simplifies to O(E + V log V) since the E term is dominated by V log V for large graphs.

Space Complexity

  1. Graph Representation: The graph is represented as an adjacency list which takes O(E) space.

  2. Distance Array: The dist array takes O(V) space.

  3. Priority Queue: The priority queue, in the worst case, can contain all nodes, thus O(V) space.

  4. DFS Stack: The recursive stack space for DFS can grow up to O(V) in the case of a deep recursion tree.

  5. Memoization: For the dfs function, a memoization cache is used, which in the worst case, can store results for each node, hence requiring O(V) space.

Combining these considerations, the overall space complexity is O(E + V) as the memoization and recursive stack space are both O(V), and the adjacency list and distance array are taken together as edge space E plus node space V.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Topological Sort Introduction

Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«