You are given an undirected, weighted, connected graph with n nodes labeled from 1 to n. The edges of the graph are provided as a list edges, where each element is of the form [u, v, weight] representing an edge between nodes u and v with a positive integer weight.
A restricted path from node 1 to node n is a path where, for every consecutive pair of nodes (u, v) along the path, the shortest distance from v to n is strictly less than that from u to n.
Your task is to return the number of restricted paths from node 1 to node n, modulo 10^9 + 7.
1 and end at node n.n" strictly decreases at every step.
The immediate challenge is to recognize that we are not just finding any path from 1 to n, but only those where each step brings us strictly closer (in terms of shortest-path distance) to n. This rules out most brute-force path enumeration approaches, especially since the graph can be large and have cycles.
A naive brute-force approach would attempt to enumerate all possible paths from 1 to n and check if each path is restricted. However, this is computationally infeasible for large graphs due to the exponential number of possible paths.
The key insight is that the "restricted" property is based on the shortest path distances to n. If we know, for every node, its shortest distance to n, we can only proceed to neighbors that are strictly closer (by shortest path) to n. This suggests a dynamic programming or memoization approach, where we count the number of restricted paths from each node, building up to the answer for node 1.
nn to compute the shortest distance from every node to n. This is necessary to enforce the "restricted" condition.
dp(u) as the number of restricted paths from node u to node n. For each node, we recursively sum the number of restricted paths from all of its neighbors whose distance to n is strictly less than that of u. We use memoization to avoid recomputing results for the same node.
dp(n) = 1, since there is exactly one path from n to itself. All results are taken modulo 10^9 + 7 as required.
dp(1), the number of restricted paths from node 1 to node n.
This approach is efficient because each node is processed only once for each possible state, and the graph traversal is guided by the decreasing distance property, avoiding cycles and redundant work.
Sample 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]]
dp(1) = dp(2) + dp(3)The key to solving the "Number of Restricted Paths From First to Last Node" problem is to leverage the shortest path distances from each node to the target node to enforce the restricted movement. By combining Dijkstra's algorithm for distance computation and memoized DFS for counting paths, we transform a potentially exponential brute-force problem into an efficient and elegant dynamic programming solution. The use of memoization ensures that each state is only computed once, and the decreasing-distance property naturally prevents cycles and redundant exploration.
from collections import defaultdict
import heapq
MOD = 10**9 + 7
class Solution:
def countRestrictedPaths(self, n, edges):
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
heap = [(0, n)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
# Memoized DFS
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(u):
if u == n:
return 1
res = 0
for v, _ in graph[u]:
if dist[v] < dist[u]:
res = (res + dfs(v)) % MOD
return res
return dfs(1)
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
int countRestrictedPaths(int n, vector<vector<int>>& edges) {
const int MOD = 1e9 + 7;
vector<vector<pair<int, int>>> graph(n + 1);
for (auto& e : edges) {
graph[e[0]].emplace_back(e[1], e[2]);
graph[e[1]].emplace_back(e[0], e[2]);
}
// Dijkstra from node n
vector<int> dist(n + 1, INT_MAX);
dist[n] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.emplace(0, n);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto& [v, w] : graph[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.emplace(dist[v], v);
}
}
}
// DP: sort by dist
vector<pair<int, int>> nodes;
for (int i = 1; i <= n; ++i) nodes.emplace_back(dist[i], i);
sort(nodes.begin(), nodes.end());
vector<int> dp(n + 1, 0);
dp[n] = 1;
for (auto& [_, u] : nodes) {
for (auto& [v, __] : graph[u]) {
if (dist[v] < dist[u]) {
dp[u] = (dp[u] + dp[v]) % MOD;
}
}
}
return dp[1];
}
};
import java.util.*;
class Solution {
public int countRestrictedPaths(int n, int[][] edges) {
final int MOD = 1000000007;
List<int[]>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
for (int[] e : edges) {
graph[e[0]].add(new int[]{e[1], e[2]});
graph[e[1]].add(new int[]{e[0], e[2]});
}
// Dijkstra from n
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[n] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, n});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
if (d > dist[u]) continue;
for (int[] nei : graph[u]) {
int v = nei[0], w = nei[1];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
// DP: sort nodes by dist
int[][] nodes = new int[n][2];
for (int i = 1; i <= n; i++) {
nodes[i - 1][0] = dist[i];
nodes[i - 1][1] = i;
}
Arrays.sort(nodes, Comparator.comparingInt(a -> a[0]));
int[] dp = new int[n + 1];
dp[n] = 1;
for (int[] node : nodes) {
int u = node[1];
for (int[] nei : graph[u]) {
int v = nei[0];
if (dist[v] < dist[u]) {
dp[u] = (dp[u] + dp[v]) % MOD;
}
}
}
return dp[1];
}
}
/**
* @param {number} n
* @param {number[][]} edges
* @return {number}
*/
var countRestrictedPaths = function(n, edges) {
const MOD = 1e9 + 7;
const graph = Array.from({length: n + 1}, () => []);
for (const [u, v, w] of edges) {
graph[u].push([v, w]);
graph[v].push([u, w]);
}
// Dijkstra from node n
const dist = new Array(n + 1).fill(Infinity);
dist[n] = 0;
const heap = [[0, n]];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]);
const [d, u] = heap.shift();
if (d > dist[u]) continue;
for (const [v, w] of graph[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
heap.push([dist[v], v]);
}
}
}
// Memoized DFS
const memo = new Array(n + 1).fill(-1);
function dfs(u) {
if (u === n) return 1;
if (memo[u] !== -1) return memo[u];
let res = 0;
for (const [v, _] of graph[u]) {
if (dist[v] < dist[u]) {
res = (res + dfs(v)) % MOD;
}
}
return memo[u] = res;
}
return dfs(1);
};