Skip to main content
Talentd

Number of Restricted Paths From First to Last Node - Solution & Explanation

MediumDynamic ProgrammingGraphTopological SortHeap (Priority Queue)12 min readAsked at: Google
Practice this problem

Problem Statement

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 * 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.

Approach Overview

Problem Overview: You are given an undirected weighted graph with n nodes. A path from node 1 to node n is restricted if the shortest distance to node n strictly decreases at every step along the path. The task is to count how many such restricted paths exist, modulo 1e9 + 7.

Approach 1: Modified Dijkstra's Algorithm with Memoization (O(E log V) time, O(V + E) space)

The key observation: whether a step is valid depends on the shortest distance from each node to node n. Compute these distances first using shortest path logic. Run Dijkstra's algorithm starting from node n so you get dist[x] = shortest distance from x to n. Once distances are known, a restricted path simply means moving from a node to a neighbor with a strictly smaller distance value.

After this preprocessing, the graph effectively becomes a directed acyclic structure if you only keep edges that go from larger dist to smaller dist. Use DFS from node 1 and count valid paths recursively. Memoization stores the number of ways to reach n from each node so each state is computed once. Every DFS step iterates through neighbors and only continues if dist[next] < dist[current]. This combines dynamic programming with graph traversal to avoid recomputation.

Approach 2: DAG Shortest Path with Topological Sorting (O(E log V + V log V) time, O(V + E) space)

After computing shortest distances to node n using Dijkstra, orient every edge from the node with larger distance to the node with smaller distance. Because distances strictly decrease, the resulting graph forms a DAG. Counting restricted paths becomes a classic DP-on-DAG problem.

Sort nodes by increasing dist value (which acts as a topological order). Initialize dp[n] = 1 because there is exactly one way to stay at node n. Traverse nodes in sorted order and propagate counts to neighbors with larger distance values in reverse direction. Each transition adds dp[next] into the current node’s count while applying modulo arithmetic. This approach removes recursion and replaces it with iterative dynamic programming over the DAG structure.

Recommended for interviews: The Dijkstra + memoized DFS approach is the one most candidates implement. It shows understanding of graph traversal, shortest paths, and DP with caching. The DAG + topological DP approach demonstrates deeper insight into how the distance constraint implicitly creates a DAG and is often discussed as an optimization or alternative explanation.

Approach 1: Approach 1: Modified Dijkstra's Algorithm with Memoization

To 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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: DAG Shortest Path with Topological Sorting

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.

Code

C++Java

C++

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n + m) for the graph representation and distance/memoization arrays.

Approach 2: DAG Shortest Path with Topological Sorting

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Modified Dijkstra + Memoized DFSO(E log V)O(V + E)General case; easiest to implement in interviews
DAG DP with Topological OrderingO(E log V + V log V)O(V + E)When you want an iterative DP solution without recursion

Video Solution

5699. Number of Restricted Paths From First to Last Node • Fraz • 4,933 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Restricted Paths From First to Last Node easy or hard?
The problem is rated Medium because it combines multiple concepts: shortest path computation, graph traversal, and dynamic programming. The tricky part is realizing that restricted paths depend on distances to node n, which must be computed first. Once that insight is clear, the remaining solution is a straightforward DP on decreasing distance edges.
Number of Restricted Paths From First to Last Node Python/Java solution
Python solutions typically combine heapq-based Dijkstra with a recursive DFS using functools.lru_cache for memoization. Java implementations use PriorityQueue for Dijkstra and either recursion with memo arrays or iterative DP on a DAG. Both approaches maintain O(E log V) time complexity.
How to solve Number of Restricted Paths From First to Last Node in O(E log V)?
First run Dijkstra starting from node n to compute the shortest distance from every node to n. Then perform DFS from node 1 and only move to neighbors whose distance value is smaller than the current node’s distance. Memoize the number of ways to reach n from each node to avoid recomputation. Combine counts modulo 1e9+7.
What is the best approach for Number of Restricted Paths From First to Last Node?
The standard solution computes shortest distances from every node to node n using Dijkstra’s algorithm, then counts valid paths using DFS with memoization. A step is allowed only if the next node has a strictly smaller distance to n. This converts the problem into dynamic programming on a directed acyclic structure. The overall complexity is O(E log V).
Is Number of Restricted Paths From First to Last Node asked at Google/Amazon/Meta?
Graph problems involving shortest paths and dynamic programming are common at companies like Google, Amazon, and Meta. This problem tests multiple concepts together: Dijkstra’s algorithm, DAG reasoning, and memoized DFS. Variants of this pattern appear frequently in senior-level interview rounds.
What data structure is used in Number of Restricted Paths From First to Last Node?
The solution uses an adjacency list to represent the graph and a min-heap priority queue for Dijkstra’s algorithm. Additional structures include a distance array storing shortest paths to node n and a memoization array for dynamic programming during DFS. These enable efficient traversal and caching of subproblems.
What is the time complexity of Number of Restricted Paths From First to Last Node?
The optimal solution runs in O(E log V) time due to the Dijkstra shortest path computation with a priority queue. The subsequent DFS with memoization visits each node and edge at most once, which is O(V + E). Space complexity is O(V + E) for the adjacency list, distance array, and memo table.

Ready to solve this problem?

Practice Number of Restricted Paths From First to Last Node with our built-in code editor and test cases.

Practice on FleetCode
Previous

All Ancestors of a Node in a Directed Acyclic Graph

Next

Design Graph With Shortest Path Calculator