Number of Ways to Arrive at Destination: Dijkstra with Path Counting

You have a city with n intersections numbered 0 to n - 1, connected by bidirectional roads. Each road has a travel time. You want to find how many different ways you can travel from intersection 0 to intersection n - 1 in the shortest possible time. Return the answer modulo 10^9 + 7.

This is LeetCode 1976: Number of Ways to Arrive at Destination, and it is one of the best problems for learning how to combine Dijkstra's shortest path algorithm with dynamic programming counting.

Source / DestinationProcessedUnvisited

Why this problem matters

Most shortest path problems ask you to find the shortest distance. This one asks you to count how many paths achieve that shortest distance. That twist forces you to augment Dijkstra's algorithm with a second array that tracks the number of ways to reach each node optimally.

This pattern, running a well-known algorithm while maintaining auxiliary state, shows up constantly in interviews. You might see it as "count the number of shortest paths in a grid," "find how many ways to reach a target with minimum cost," or any variant where the answer is not just the optimal value but the number of ways to achieve it. Once you internalize the dual-array technique here, you can apply it wherever Dijkstra meets counting.

The key insight

Standard Dijkstra maintains a dist[] array. For this problem, you maintain a second array ways[] alongside it. When you relax an edge to a neighbor:

• If you find a strictly shorter path, update dist[neighbor] and replace ways[neighbor] with ways[current]. You have found a new best, so all previous path counts are obsolete.
• If you find a path with equal distance, add ways[current] to ways[neighbor]. You have discovered additional routes that tie for shortest.
• If the path is longer, skip it entirely.

Initialize dist[0] = 0 and ways[0] = 1 (there is exactly one way to be at the start with zero distance). Everything else starts at infinity with zero ways.

The solution

import heapq
from collections import defaultdict

def count_paths(n: int, roads: list[list[int]]) -> int:
    MOD = 10**9 + 7

    graph = defaultdict(list)
    for u, v, t in roads:
        graph[u].append((v, t))
        graph[v].append((u, t))

    dist = [float("inf")] * n
    ways = [0] * n
    dist[0] = 0
    ways[0] = 1

    heap = [(0, 0)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            new_dist = d + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                ways[v] = ways[u]
                heapq.heappush(heap, (new_dist, v))
            elif new_dist == dist[v]:
                ways[v] = (ways[v] + ways[u]) % MOD

    return ways[n - 1] % MOD

The structure follows standard Dijkstra almost exactly. You build an adjacency list (bidirectional, since roads go both ways), initialize distances and the heap, then process nodes in order of distance. The only additions are the ways[] array and the two-branch update logic inside the neighbor loop.

When you pop a node from the heap, you first check if d > dist[u]. This is a stale entry check. Because we push to the heap without removing old entries, a node might appear multiple times. If the popped distance is larger than the current best, this entry is outdated and we skip it.

For each neighbor v, you compute new_dist = d + w. If this is strictly less than dist[v], you have found a shorter path. You replace both dist[v] and ways[v], and push the neighbor onto the heap. If new_dist equals dist[v], you have found another shortest path, so you add the current node's way count to the neighbor's.

Visual walkthrough

Let's trace through Dijkstra with path counting on a small graph. We have 4 nodes (0 to 3) with edges: 0-1 (weight 1), 0-2 (weight 2), 1-2 (weight 1), 2-3 (weight 2). There are two shortest paths from 0 to 3, both with total distance 4.

The critical moment is Step 2. When we process node 1 and look at neighbor 2, the new distance (1 + 1 = 2) equals dist[2] which is already 2. This means we have discovered a second shortest path to node 2. Instead of replacing ways[2], we add ways[1] to it, making ways[2] = 2. Later, when node 2 relaxes node 3, it passes along both of its paths, so ways[3] inherits the value 2.

Complexity analysis

N is the number of intersections, E is the number of roads.

Time: Each node is processed at most once. Each edge relaxation involves a heap push costing O(log N). With E edges (each bidirectional, so 2E directed entries), the total work is O(E log N). Processing all heap pops adds O(N log N). Combined: O((N + E) log N).

Space: The adjacency list stores O(E) entries. The dist[] and ways[] arrays each take O(N). The heap can hold at most O(E) entries in the worst case. Total: O(N + E).

Edge cases

• Source equals destination: if n = 1, there is one intersection and zero roads. The answer is 1 (you are already there). ways[0] = 1 handles this naturally.
• Single path: if the graph has only one path from 0 to n - 1, the answer is 1. The ways[] array will never hit the equal-distance branch.
• Large answer: the number of paths can be astronomically large. The modulo 10^9 + 7 keeps the count manageable. Apply it every time you add to ways[].
• Disconnected graph: if n - 1 is unreachable from 0, dist[n - 1] stays at infinity and ways[n - 1] stays at 0.
• Multiple edges with same weight: two roads between the same pair of intersections with the same travel time create distinct paths, and the counting logic handles this correctly because each relaxation is independent.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. Dijkstra's shortest path algorithm

The foundation is standard Dijkstra's with a min-heap. You maintain a distance array, pop the closest unprocessed node, and relax its neighbors:

import heapq

def dijkstra(graph, n, source):
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))

    return dist

This core pattern handles any single-source shortest path problem on a graph with non-negative weights. The stale-entry check (if d > dist[u]) replaces the need for a decrease-key operation in the heap.

2. Path counting with dynamic programming

The counting logic follows a DP principle: the number of optimal paths to a node equals the sum of optimal paths through each of its predecessors (on shortest paths). The recurrence is:

if new_dist < dist[v]:
    dist[v] = new_dist
    ways[v] = ways[u]
elif new_dist == dist[v]:
    ways[v] += ways[u]

This is the same idea behind counting paths in a DAG, except here Dijkstra's processing order ensures you handle nodes in non-decreasing distance order, which gives you the correct DP evaluation sequence. You never need to revisit a finalized node's way count.

Common mistakes

1. Forgetting the modulo on the addition. When ways[v] += ways[u], you must apply % MOD. Without it, the count overflows for large inputs. The modulo only applies to the addition case, not when you replace ways[v] with ways[u] (since that value is already within range).

2. Replacing ways when you should add. When new_dist == dist[v], you must add ways[u] to ways[v], not replace it. Replacing it would throw away previously counted paths.

3. Skipping the stale-entry check. Without if d > dist[u]: continue, you process outdated heap entries. This leads to double-counting because a node that was already finalized gets its neighbors relaxed again with an old distance.

4. Using a visited set instead of the stale check. A simple boolean visited set works for standard Dijkstra, but for path counting you need the stale check (d > dist[u]). The reason is subtle: with lazy deletion, duplicate heap entries for the same node are harmless only if you skip them properly. A visited set would also work, but the distance comparison is more idiomatic for this variant.

5. Treating the graph as directed. The roads are bidirectional. You must add edges in both directions when building the adjacency list.

From understanding to recall

You have traced through the algorithm and seen how the two-branch update logic propagates path counts through the graph. The key detail is small: one if for shorter, one elif for equal. But under interview pressure, mixing up "replace" versus "add" is a real risk.

Spaced repetition locks this distinction into muscle memory. You practice writing the dist[] and ways[] initialization, the heap loop, and the two-branch neighbor update from scratch at increasing intervals. After a few rounds, the pattern becomes automatic. When you see a shortest path counting problem, you do not pause to rederive it. You just write it.

Related posts

• Network Delay Time - Classic Dijkstra's algorithm for shortest paths in weighted graphs
• Cheapest Flights Within K Stops - Modified shortest path with constraints
• Path with Minimum Effort - Dijkstra variant with different edge weight semantics

CodeBricks breaks Number of Ways to Arrive at Destination into its Dijkstra and path-counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a counting-on-shortest-paths problem shows up in your interview, you do not think about it. You just write it.