Number Of Restricted Paths From First To Last Node - Leetcode Solution

Problem Statement:

You are given an integer n and an array edges where edges[i] = [ui, vi] represents a bidirectional edge between nodes ui and vi in the graph.

A path is called restricted if it satisfies the following conditions:

• The path contains at most 2 edges.
• The path does not contain any node that is repeated.
• The path does not contain any cycles (or closed paths).
• The edge between nodes u and v is only used in the path if there are no other edges between nodes u and v.

Return the number of restricted paths from the first to the last node in the graph. Since the answer may be too large, return it modulo 109 + 7.

Solution:

Approach:

• Create adjacency matrix of graph
• Calculate shorted path matrix
• Use dynamic programming to get restricted path count

Algorithm:

• Create adjacency matrix of graph

• Calculate shorted path matrix

• Create matrix dist[] where dist[i][j] represents shortest distance between i and j

• Initialize all elements of dist[][] matrix with infinity, except diagonal elements(dist[i][i] = 0)

• For each edge (u, v) in edges[] array, update dist[u][v] and dist[v][u] with edge weight = 1 since it is an unweighted graph

• Use Floyd Warshall Algorithm to calculate shortest distance matrix dist[][]

• Create a 2D DP matrix, dp[][] where dp[i][j] represents the number of restricted paths from i to j.

• Initially, all values of dp[][] are set to zero, except for dp[0][0] is set to 1, since path of length 0 from the first to the first node is possible(which is the starting node).

• For every path between the i-th node and the j-th node, check whether they fulfill the conditions of being a restricted path.

• If there is a path of length 1(i.e. direct edge) between i and j, then it is restricted path, so increment dp[i][j] by 1.

• If there is a path of length 2 between i and j, (i.e. path i-u-j, where u is an intermediate node), then check whether u is not equal to i and j and also whether there is no other direct edge between i and u or between j and u.

• If the conditions are satisfied, then dp[i][j] is incremented by the number of restricted paths from i to u.

• The final answer is dp[0][n-1] i.e. number of restricted paths from the first to the last node.

Time Complexity: O(n^3)

Space Complexity: O(n^2)

Python code implementation:

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        # Step 1: Create adjacency matrix of graph
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        adj_matrix = [[float("inf") for _ in range(n+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            adj_matrix[i][i] = 0
        for u, v in edges:
            adj_matrix[u][v] = 1
            adj_matrix[v][u] = 1

        # Step 2: Calculate shorted path matrix
        for k in range(1, n+1):
            for i in range(1, n+1):
                for j in range(1, n+1):
                    if adj_matrix[i][k] != float("inf") and adj_matrix[k][j] != float("inf"):
                        adj_matrix[i][j] = min(adj_matrix[i][j], adj_matrix[i][k] + adj_matrix[k][j])

        # Step 3: Use dynamic programming to get restricted path count
        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
        dp[0][1] = 1  # path of length 0 from first to first node is possible

        for dist in range(1, n):
            for u in range(1, n+1):
                if u == n:
                    continue
                for v in graph[u]:
                    if adj_matrix[v][n] < adj_matrix[u][n]:
                        dp[u][dist+1] = (dp[u][dist+1] + dp[v][dist]) % (10**9 + 7)

        return dp[1][n]

1