Reachable Nodes In Subdivided Graph

Reachable Nodes In Subdivided Graph

What is this problem about?

The Reachable Nodes In Subdivided Graph problem gives you a graph where each edge has cnt extra nodes inserted along it. You start at node 0 with maxMoves moves. Find how many original AND inserted nodes you can reach. This hard coding problem applies Dijkstra's algorithm to find reachable distances, then counts accessible nodes on each edge. The shortest path, graph, and heap interview pattern is the core.

Why is this asked in interviews?

Yugabyte, PhonePe, and Google ask this because it requires extending standard Dijkstra with edge-based counting — the number of intermediate nodes accessible on an edge depends on how many moves remain after reaching each endpoint.

Algorithmic pattern used

Dijkstra + edge node counting. Run Dijkstra from node 0 to get dist[v] = minimum moves to reach each original node. For each edge (u, v, cnt): nodes reachable from u on this edge = max(0, maxMoves - dist[u]). From v: max(0, maxMoves - dist[v]). Total reachable on this edge = min(cnt, from_u + from_v). Sum: all reachable original nodes (where dist[v] <= maxMoves) + all reachable inserted nodes.

Example explanation

edges=[(0,1,5),(1,2,4),(2,3,1),(2,5,0),(0,5,4),(4,5,3)], maxMoves=17, n=6. Run Dijkstra from node 0. dist=[0,6,10,12,...]. Count reachable originals (dist ≤ 17) + inserted nodes per edge.

Common mistakes candidates make

• Not running Dijkstra first (can't know remaining moves without distances).
• Counting inserted nodes on an edge multiple times.
• Off-by-one: min(cnt, from_u + from_v) caps at cnt (can't exceed the edge's nodes).
• Not handling unreachable nodes (dist = infinity).

Interview preparation tip

Reachable Nodes in Subdivided Graph extends Dijkstra with per-edge post-processing. After Dijkstra, each edge contributes its accessible intermediate nodes as min(cnt, max(0, maxMoves-dist[u]) + max(0, maxMoves-dist[v])). Practice "extended Dijkstra" problems where you need to count additional resources along the path, not just shortest path lengths.