Number of Restricted Paths From First to Last Node

Number of Restricted Paths From First to Last Node

What is this problem about?

The Number of Restricted Paths From First to Last Node problem gives you a weighted undirected graph. Define distToLastNode[v] as the shortest path from v to the last node. A path from node 1 to node n is "restricted" if distToLastNode[u] > distToLastNode[v] for every consecutive pair (u,v) on the path. Count all restricted paths modulo 10^9+7. This coding problem combines Dijkstra with DP on a DAG.

Why is this asked in interviews?

Google asks this because it requires two phases: Dijkstra to compute all-nodes shortest distances to node n, then DP on the resulting DAG (where edges go from higher-dist to lower-dist nodes). The shortest path, graph, topological sort, heap, and dynamic programming interview pattern is fully exercised.

Algorithmic pattern used

Dijkstra + memoized DFS (DP on DAG). First, run Dijkstra from node n on the reversed graph (or undirected edges) to get dist[v] for all nodes. Then count paths from 1 to n where each step goes to a node with strictly smaller dist value — this forms a DAG. Use memoized DFS: dp[v] = number of restricted paths from v to n.

Example explanation

Graph: 1-2(2), 1-3(1), 2-3(1), 2-4(3), 3-4(2). Last node=4. Dijkstra from 4: dist[4]=0, dist[3]=2, dist[2]=3, dist[1]=3. Wait: dist[1]: 1→3→4=3, or 1→2→3→4=4. dist[1]=3. dist[2]: 2→3→4=3, or 2→4=3. dist[2]=3. Restricted path from 1 to 4: each step must decrease dist. dist[1]=3=dist[2], so 1→2 not valid (not strictly decreasing). 1→3 (dist[3]=2<3 ✓). 3→4 (dist[4]=0<2 ✓). dp[1]=1. Answer=1.

Common mistakes candidates make

• Running Dijkstra from node 1 instead of from node n.
• Not memoizing the DP (exponential recomputation).
• Allowing equal-dist steps (must be strictly less than).
• Building the DAG explicitly instead of using memoized DFS on the dist-based DAG.

Interview preparation tip

"Shortest path + count paths" problems always have two phases. The Dijkstra phase establishes a distance ordering; the DP phase counts paths along this ordering. The DAG property follows from the strictly decreasing distance constraint — no cycles are possible. Practice these two-phase problems: they appear in Dijkstra/BFS counting variants and are excellent interview signals for graph mastery.