LeetCode 1786 - Number of Restricted Paths From First to Last Node

This problem gives us an undirected weighted graph with n nodes labeled from 1 to n. Every edge connects two nodes and has a positive weight. The graph is guaranteed to be connected, meaning there is always at least one path between any pair of nodes.

leetcodemediumdynamic-programminggraph-theorytopological-sortheap-(priority-queue)shortest-path

LeetCode Problem 1786

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Graph Theory, Topological Sort, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

This problem gives us an undirected weighted graph with n nodes labeled from 1 to n. Every edge connects two nodes and has a positive weight. The graph is guaranteed to be connected, meaning there is always at least one path between any pair of nodes.

The goal is not simply to count all paths from node 1 to node n. Instead, we only count paths that satisfy a special restriction involving shortest path distances.

For every node x, define:

distanceToLastNode(x)

as the shortest possible distance from node x to node n.

A path is considered a restricted path if, while moving along the path, the shortest distance to node n strictly decreases at every step.

Suppose we have a path:

z0 -> z1 -> z2 -> ... -> zk

where z0 = 1 and zk = n.

The path is restricted if:

distanceToLastNode(zi) > distanceToLastNode(zi+1)

for every adjacent pair of nodes.

This means every move must bring us strictly closer to node n in terms of shortest path distance.

The important detail is that the restriction is based on shortest path distances, not direct edge weights.

What the Input Represents

The input consists of:

  • n, the number of nodes
  • edges, where each edge is represented as:
[ui, vi, weighti]

This means there is an undirected edge between ui and vi with cost weighti.

The graph may contain cycles, multiple possible shortest paths, and many different valid restricted paths.

What the Output Means

We must return the number of restricted paths from node 1 to node n.

Since the number of paths can become very large, the answer must be returned modulo:

10^9 + 7

Constraints and Their Implications

The constraints are:

  • 1 <= n <= 2 * 10^4
  • n - 1 <= edges.length <= 4 * 10^4

This graph is relatively large. A brute-force enumeration of all possible paths is impossible because the number of paths can grow exponentially.

The edge weights are positive:

1 <= weighti <= 10^5

This is important because it means Dijkstra's algorithm can safely compute shortest paths efficiently.

The graph is connected, so shortest distances from every node to node n always exist.

Important Edge Cases

One important edge case is a graph with many cycles. A naive DFS that explores all paths without careful pruning could revisit nodes repeatedly and explode exponentially.

Another important case is when multiple nodes have the same shortest distance to node n. Since the restriction requires strictly decreasing distances, transitions between equal-distance nodes are not allowed.

A third edge case is when there is only one valid restricted path despite many graph connections. The algorithm must avoid counting invalid routes that temporarily move farther away.

A final important case is a graph shaped like a tree. In this situation, there is exactly one simple path between any pair of nodes, but not all such paths are necessarily restricted.

Approaches

Brute Force Approach

A straightforward idea is to generate every possible path from node 1 to node n using DFS or backtracking.

For each path, we could first compute all shortest distances to node n, then verify whether the path satisfies the restriction that distances strictly decrease at every step.

This approach is correct because it explicitly checks every candidate path and counts only valid ones.

However, it is far too slow.

Graphs can contain cycles and exponentially many simple paths. Even with pruning, the number of possible paths can become enormous. Since n can be as large as 20000, exhaustive path enumeration is infeasible.

Key Insight

The key observation is that shortest path distances create a natural ordering on the graph.

If we compute:

dist[x] = shortest distance from x to n

then every restricted path must move from a node with larger dist to a node with smaller dist.

This transforms the problem into counting paths in a directed acyclic structure.

Even though the original graph may contain cycles, once we only allow edges that move to strictly smaller distances, cycles become impossible because distances continuously decrease.

This allows dynamic programming.

The optimal strategy is:

  1. Use Dijkstra's algorithm from node n to compute shortest distances to every node.
  2. Use DFS + memoization to count restricted paths.
  3. From each node, only move to neighbors with strictly smaller shortest distances.

This avoids recomputation and guarantees efficiency.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(n) Enumerates all possible paths
Optimal O((V + E) log V) O(V + E) Dijkstra + memoized DFS

Algorithm Walkthrough

Step 1: Build the Graph

Create an adjacency list representation of the graph.

Each node stores pairs:

(neighbor, weight)

An adjacency list is efficient because the graph is sparse:

E <= 4 * 10^4

Step 2: Compute Shortest Distances Using Dijkstra

Run Dijkstra's algorithm starting from node n.

This computes:

dist[x]

which is the shortest distance from node x to node n.

We use a priority queue because all edge weights are positive.

The result gives us the ordering needed for restricted paths.

Step 3: Define the DP State

Let:

dp[x]

represent the number of restricted paths from node x to node n.

Our final answer will be:

dp[1]

Step 4: DFS Transition

For every neighbor of node x:

  • If:
dist[neighbor] < dist[x]

then moving to that neighbor is allowed in a restricted path.

Therefore:

dp[x] += dp[neighbor]

Step 5: Base Case

At node n, there is exactly one restricted path to itself:

dp[n] = 1

Step 6: Memoization

Without memoization, DFS would repeatedly recompute the same states.

We store previously computed values in a cache so each node is processed only once.

Step 7: Return the Result

Return:

dp[1] % MOD

where:

MOD = 10^9 + 7

Why it works

The correctness comes from the fact that shortest distances strictly decrease along every restricted path.

Because distances strictly decrease, cycles cannot occur in the restricted graph. This effectively creates a DAG structure.

The DFS recurrence considers every valid next step exactly once, and memoization ensures each subproblem is solved only once.

Since every restricted path must follow decreasing distances, and every decreasing-distance transition is explored, the algorithm counts all valid restricted paths exactly once.

Python Solution

from typing import List
from collections import defaultdict
import heapq
from functools import lru_cache

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        MOD = 10**9 + 7

        graph = defaultdict(list)

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        # Dijkstra from node n
        dist = [float('inf')] * (n + 1)
        dist[n] = 0

        min_heap = [(0, n)]

        while min_heap:
            current_dist, node = heapq.heappop(min_heap)

            if current_dist > dist[node]:
                continue

            for neighbor, weight in graph[node]:
                new_dist = current_dist + weight

                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    heapq.heappush(min_heap, (new_dist, neighbor))

        @lru_cache(None)
        def dfs(node: int) -> int:
            if node == n:
                return 1

            total_paths = 0

            for neighbor, _ in graph[node]:
                if dist[neighbor] < dist[node]:
                    total_paths += dfs(neighbor)
                    total_paths %= MOD

            return total_paths

        return dfs(1)

The implementation begins by constructing an adjacency list for the undirected weighted graph.

Next, Dijkstra's algorithm computes the shortest distance from every node to node n. The priority queue always expands the currently closest node, guaranteeing correct shortest distances because all edge weights are positive.

After shortest distances are known, the problem becomes a directed traversal problem. From any node, we are only allowed to move to neighbors with strictly smaller shortest distances.

The dfs function computes the number of restricted paths starting from a given node.

The recursion terminates at node n, where exactly one valid path exists.

Memoization with lru_cache ensures every node's result is computed once, reducing the complexity dramatically.

Go Solution

package main

import (
	"container/heap"
	"math"
)

const MOD int = 1e9 + 7

type Edge struct {
	to     int
	weight int
}

type Item struct {
	node int
	dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].dist < pq[j].dist
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}

func countRestrictedPaths(n int, edges [][]int) int {
	graph := make([][]Edge, n+1)

	for _, e := range edges {
		u, v, w := e[0], e[1], e[2]

		graph[u] = append(graph[u], Edge{v, w})
		graph[v] = append(graph[v], Edge{u, w})
	}

	// Dijkstra from node n
	dist := make([]int, n+1)

	for i := 1; i <= n; i++ {
		dist[i] = math.MaxInt64
	}

	dist[n] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, Item{n, 0})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(Item)

		node := current.node
		currentDist := current.dist

		if currentDist > dist[node] {
			continue
		}

		for _, edge := range graph[node] {
			neighbor := edge.to
			newDist := currentDist + edge.weight

			if newDist < dist[neighbor] {
				dist[neighbor] = newDist
				heap.Push(pq, Item{neighbor, newDist})
			}
		}
	}

	memo := make([]int, n+1)

	for i := 0; i <= n; i++ {
		memo[i] = -1
	}

	var dfs func(int) int

	dfs = func(node int) int {
		if node == n {
			return 1
		}

		if memo[node] != -1 {
			return memo[node]
		}

		total := 0

		for _, edge := range graph[node] {
			neighbor := edge.to

			if dist[neighbor] < dist[node] {
				total += dfs(neighbor)
				total %= MOD
			}
		}

		memo[node] = total
		return total
	}

	return dfs(1)
}

The Go implementation follows the same overall strategy as the Python version.

One important difference is that Go does not provide a built-in priority queue, so we implement one using the container/heap package.

Memoization is implemented manually using a slice initialized with -1, instead of Python's lru_cache.

The distance array uses math.MaxInt64 as an effectively infinite initial value.

Worked Examples

Example 1

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

Step 1: Compute Shortest Distances

Running Dijkstra from node 5 gives:

Node Shortest Distance to 5
1 4
2 2
3 1
4 6
5 0

Step 2: Allowed Transitions

A move is allowed only if distance decreases.

From To Allowed?
1 2 Yes, 4 > 2
1 3 Yes, 4 > 1
1 4 No, 4 < 6
2 3 Yes, 2 > 1
2 5 Yes, 2 > 0
3 5 Yes, 1 > 0

Step 3: DFS Computation

Start from node 5:

dp[5] = 1

Node 3:

dp[3] = dp[5] = 1

Node 2:

dp[2] = dp[3] + dp[5]
      = 1 + 1
      = 2

Node 1:

dp[1] = dp[2] + dp[3]
      = 2 + 1
      = 3

Final answer:

3

Example 2

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]
]

Step 1: Compute Distances

Node Shortest Distance to 7
1 5
2 6
3 4
4 7
5 3
6 2
7 0

Step 2: Valid Restricted Moves

From To
1 3
3 7
2 5
2 6
5 6
5 7
6 7

Step 3: Count Paths

dp[7] = 1
dp[6] = 1
dp[5] = 2
dp[3] = 1
dp[1] = 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O((V + E) log V) Dijkstra dominates the runtime
Space O(V + E) Graph storage, distance array, memoization

The graph contains V vertices and E edges.

Dijkstra's algorithm using a binary heap runs in:

O((V + E) log V)

The DFS with memoization processes each node once and each edge at most once, contributing:

O(V + E)

Since Dijkstra dominates, the final complexity remains:

O((V + E) log V)

The adjacency list, memo table, recursion stack, and distance array together require linear space.

Test Cases

from typing import List

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        from collections import defaultdict
        import heapq
        from functools import lru_cache

        MOD = 10**9 + 7

        graph = defaultdict(list)

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        dist = [float('inf')] * (n + 1)
        dist[n] = 0

        heap = [(0, n)]

        while heap:
            d, node = heapq.heappop(heap)

            if d > dist[node]:
                continue

            for nei, w in graph[node]:
                nd = d + w

                if nd < dist[nei]:
                    dist[nei] = nd
                    heapq.heappush(heap, (nd, nei))

        @lru_cache(None)
        def dfs(node):
            if node == n:
                return 1

            total = 0

            for nei, _ in graph[node]:
                if dist[nei] < dist[node]:
                    total += dfs(nei)

            return total % MOD

        return dfs(1)

sol = Solution()

# Example 1
assert sol.countRestrictedPaths(
    5,
    [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
) == 3

# Example 2
assert sol.countRestrictedPaths(
    7,
    [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
) == 1

# Smallest possible connected graph
assert sol.countRestrictedPaths(
    2,
    [[1,2,1]]
) == 1

# Linear chain
assert sol.countRestrictedPaths(
    4,
    [[1,2,1],[2,3,1],[3,4,1]]
) == 1

# Multiple restricted paths
assert sol.countRestrictedPaths(
    4,
    [[1,2,1],[1,3,1],[2,4,1],[3,4,1]]
) == 2

# Graph with cycles
assert sol.countRestrictedPaths(
    5,
    [[1,2,1],[2,3,1],[3,1,1],[3,4,1],[4,5,1]]
) == 1

# Equal shortest distances prevent transitions
assert sol.countRestrictedPaths(
    4,
    [[1,2,1],[1,3,1],[2,4,1],[3,4,1],[2,3,1]]
) == 2

# Dense graph stress case
assert sol.countRestrictedPaths(
    5,
    [[1,2,1],[1,3,2],[1,4,3],[2,3,1],[2,5,4],[3,4,1],[3,5,2],[4,5,1]]
) == 5

Test Summary

Test Why
Example 1 Validates multiple restricted paths
Example 2 Validates single valid path
Two-node graph Smallest valid connected graph
Linear chain Simple monotonic structure
Multiple branching paths Ensures DP counts all valid routes
Graph with cycles Verifies cycle handling
Equal shortest distances Ensures strict inequality is enforced
Dense graph Stress-tests path counting

Edge Cases

One important edge case occurs when neighboring nodes have equal shortest distances to node n. Since restricted paths require strictly decreasing distances, transitions between equal-distance nodes are invalid. A common bug is using <= instead of <. The implementation correctly uses strict comparison:

if dist[neighbor] < dist[node]:

Another important edge case is graphs containing cycles. The original graph may contain many loops, which could cause infinite recursion or repeated counting in naive DFS implementations. The decreasing-distance rule guarantees that recursive calls always move toward smaller distances, so cycles cannot appear in the restricted traversal graph.

A third important edge case is when the graph contains only one possible restricted path even though many physical paths exist. Some routes may temporarily move farther from node n, making them invalid. The algorithm correctly filters these paths using the shortest-distance ordering before counting them.

A final edge case is very large graphs near the constraint limits. Recursive brute-force search would time out due to exponential growth. The combination of Dijkstra's algorithm and memoized DFS ensures every node and edge is processed efficiently, keeping the solution within acceptable limits.