Reachable Nodes in Subdivided Graph: Modified Dijkstra

You are given an undirected graph with n nodes (labeled 0 to n - 1) and an edge list edges[i] = [ui, vi, cnti], meaning there is an edge between ui and vi that has been subdivided into cnti + 1 segments by inserting cnti new nodes along it. Starting from node 0, you can make at most maxMoves moves. Each move traverses one edge segment. Return the maximum number of nodes (both original and subdivided) you can reach.

This is LeetCode 882: Reachable Nodes In Subdivided Graph, a hard problem that combines Dijkstra's shortest path algorithm with a clever counting step. If you already know how to run Dijkstra on a weighted graph, this problem teaches you how to adapt that template when the graph has been modified in a structured way.

Why this problem matters

This problem is a masterclass in reducing an unfamiliar structure to a familiar one. At first glance, the subdivided graph looks like it could have millions of nodes. Building the full expanded graph would be too slow. But you do not need to. The key insight is that Dijkstra only needs to run on the original graph. The subdivided nodes are counted afterward using simple arithmetic.

This pattern of "run a standard algorithm on a compressed representation, then handle the details" shows up in many graph problems. Once you see it here, you will recognize it in other problems where the graph is too large to materialize but has exploitable structure.

The approach: Dijkstra on the original graph, then count

The subdivided graph has potentially huge numbers of nodes, but it is built from a small set of original nodes and edges. The trick is to treat each edge's weight as cnt + 1 (the number of segments you need to traverse to cross the entire edge) and run Dijkstra on the original graph.

Here is the plan:

1. Build a weighted adjacency list from the edges. For each edge [u, v, cnt], the weight from u to v (and v to u) is cnt + 1.
2. Run Dijkstra from node 0 to find the shortest distance to every reachable original node.
3. Count reachable original nodes: any original node with dist[node] at most maxMoves is reachable.
4. Count reachable subdivided nodes per edge: for each edge [u, v, cnt], compute how many subdivided nodes you can reach from each endpoint. From u, you have maxMoves - dist[u] remaining moves. You can reach min(remaining, cnt) subdivided nodes from the u side. Similarly from v. The total reachable on that edge is min(fromU + fromV, cnt) to avoid double-counting nodes reachable from both directions.

The min(fromU + fromV, cnt) clamp is critical. If both endpoints have enough remaining moves, their reachable ranges overlap in the middle. You cannot count those middle nodes twice, and you also cannot count more than cnt subdivided nodes on a single edge.

The solution

import heapq
from collections import defaultdict

def reachableNodes(edges, maxMoves, n):
    graph = defaultdict(list)
    for u, v, cnt in edges:
        graph[u].append((v, cnt + 1))
        graph[v].append((u, cnt + 1))

    dist = {}
    heap = [(0, 0)]

    while heap:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue
        dist[node] = d
        for neighbor, weight in graph[node]:
            if neighbor not in dist:
                heapq.heappush(heap, (d + weight, neighbor))

    result = sum(1 for node in dist if dist[node] <= maxMoves)

    for u, v, cnt in edges:
        from_u = min(maxMoves - dist[u], cnt) if u in dist and dist[u] <= maxMoves else 0
        from_v = min(maxMoves - dist[v], cnt) if v in dist and dist[v] <= maxMoves else 0
        result += min(from_u + from_v, cnt)

    return result

Visual walkthrough

Let's trace through the algorithm on edges = [[0,1,4], [0,2,2], [1,2,1]] with maxMoves = 6 and n = 3. Edge weights for Dijkstra become 5, 3, and 2 respectively.

The first three steps are standard Dijkstra. The final step is where this problem differs from typical shortest path problems: you iterate over each edge and use the remaining moves from each endpoint to count how many subdivided nodes are reachable. The min(fromU + fromV, cnt) prevents double-counting.

Complexity analysis

Time: Dijkstra runs in O(E log N) where E is the number of edges and N is the number of original nodes. After Dijkstra, iterating over all edges to count subdivided nodes takes O(E). The dominant term is O(E log N).

Space: The adjacency list stores all edges, taking O(N + E). The heap holds at most O(E) entries. The distance dictionary holds at most N entries. Total space is O(N + E).

Building blocks

Dijkstra's shortest path algorithm. This problem uses the standard Dijkstra template with a min-heap. The only modification is the edge weight: instead of using the given weight directly, each edge's weight is cnt + 1. If you are comfortable with Dijkstra on problems like Network Delay Time, the core loop here is identical.

Post-Dijkstra counting on edges. The novel piece is the counting step after Dijkstra finishes. For each edge [u, v, cnt], you compute how far you can reach from each side and clamp the total to cnt. This is a pattern you will see in problems where the "real" graph is a compressed version of a larger structure. The algorithm runs on the compressed graph, and then you expand the answer using the structure's properties.

Edge cases to watch for

• Disconnected nodes: if a node is unreachable from node 0, dist will not contain it. Make sure to check whether a node is in dist before computing remaining moves. Unreachable endpoints contribute 0 subdivided nodes from their side.
• maxMoves is 0: you can only reach node 0 itself. No moves means no subdivided nodes and no other original nodes. The answer is 1.
• An edge with cnt = 0: this edge has no subdivided nodes. It acts like a normal edge of weight 1 in the Dijkstra graph. The counting step adds 0 for this edge, which is correct.
• Both endpoints can reach all subdivided nodes: if from_u + from_v exceeds cnt, the clamping with min(from_u + from_v, cnt) prevents overcounting. For example, if cnt = 4 and both endpoints can reach 3 subdivided nodes from their side, the answer for that edge is min(3 + 3, 4) = 4, not 6.
• Large cnt values: individual edges can have up to 10^4 subdivided nodes. You never build these nodes explicitly, so memory is not an issue. The arithmetic handles it.

From understanding to recall

You have seen how this problem reduces to Dijkstra plus a counting step. The Dijkstra part is standard. The counting part has one formula: min(from_u + from_v, cnt). That formula encodes double-counting prevention, and it is easy to forget under pressure.

The best way to lock this in is to practice the two-phase structure: run Dijkstra on the compressed graph, then iterate over edges to expand the answer. If you can write the Dijkstra loop from memory (which you should drill separately on problems like Network Delay Time), then the only new piece to memorize is the per-edge counting logic. Spaced repetition on that formula and the edge-case checks will make it second nature.

Related posts

• Network Delay Time - The foundational Dijkstra problem
• Cheapest Flights Within K Stops - Modified Dijkstra with constraints
• Swim in Rising Water - Graph search with a priority queue