Number of Ways to Arrive at Destination — Dijkstra With Path Counts [LC 1976, Google, Amazon]

Problem Statement#

You are at intersection 0 in a city with n intersections numbered 0..n-1 and bi-directional roads roads[i] = [u, v, time]. Return the number of ways to travel from intersection 0 to intersection n - 1 in the shortest amount of time, modulo 10^9 + 7.

Constraints:

• 1 <= n <= 200
• n - 1 <= roads.length <= n * (n - 1) / 2
• 1 <= time <= 10^9
• Answer fits in 32-bit when reduced modulo 10^9 + 7.

Example 1:

Input:  n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],
                        [3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: Shortest time is 7. Four distinct routes achieve it:
  0 -> 6, 0 -> 4 -> 6, 0 -> 1 -> 2 -> 5 -> 6, 0 -> 1 -> 3 -> 5 -> 6.

Example 2:

Input:  n = 2, roads = [[1,0,10]]
Output: 1

Why This Problem Matters#

LeetCode 1976 is one of the cleanest tests of whether a candidate truly understands Dijkstra's algorithm. Many engineers can run Dijkstra to compute shortest distances; far fewer can extend it to count the number of distinct shortest paths. The extension is two lines of code but reveals deep understanding of relaxation order, monotonicity, and the overlap between graph algorithms and dynamic programming.

Google, Amazon, Meta, and Uber all ask shortest-path-counting variants because they appear in production: counting equally-good driving routes, A/B testing eligible matchmaking paths, splitting traffic evenly across shortest network links, and explaining "why we chose this route" in mapping apps. The pattern also generalises to "count shortest paths visiting all of S" and "shortest path with the most/fewest hops as tiebreaker," all of which boil down to maintaining a parallel count[] array next to dist[].

The interview signal is unambiguous: if you correctly say "when we relax (u, v) and find a strictly shorter distance to v, replace count[v] = count[u]; if we find an equal distance, add count[v] += count[u]," you have demonstrated mastery of Dijkstra at the level senior engineers care about.

The Core Insight#

Run standard Dijkstra from source 0 to compute dist[v] = the shortest time to each node v. Maintain a parallel ways[v] = number of shortest paths from source to v. Initialise dist[src] = 0, ways[src] = 1.

When we pop (d, u) from the min-heap and explore an edge (u, v, w):

• If d + w < dist[v]: we discovered a strictly better path. Update dist[v] = d + w and ways[v] = ways[u] (we inherit the count from u because every shortest path to u extends uniquely to v).
• If d + w == dist[v]: we found another shortest path to v. Increment ways[v] += ways[u] modulo 10^9 + 7.
• If d + w > dist[v]: ignore.

The non-negativity of weights guarantees Dijkstra processes nodes in order of finalised distance. By the time we dequeue u, dist[u] is final and ways[u] is fully accumulated — no later relaxation can change it. This is the cornerstone of the extension's correctness; it would fail with negative edges (where Bellman-Ford with topological iteration is required instead).

Complexity: O((V + E) log V) time, O(V + E) space.

Visual Dry Run#

n = 4, roads = [[0,1,1], [0,2,1], [1,3,1], [2,3,1]] (a diamond).

Two shortest paths: 0 -> 1 -> 3 and 0 -> 2 -> 3. The answer is 2.

Solution (Optimal)#

Python — Dijkstra + path count#

import heapq
 
MOD = 10 ** 9 + 7
 
def countPaths(n, roads):
    adj = [[] for _ in range(n)]
    for u, v, w in roads:
        adj[u].append((v, w))
        adj[v].append((u, w))
 
    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 adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                ways[v] = ways[u]
                heapq.heappush(heap, (nd, v))
            elif nd == dist[v]:
                ways[v] = (ways[v] + ways[u]) % MOD
    return ways[n - 1]

JavaScript — Dijkstra + path count#

function countPaths(n, roads) {
    const MOD = 1_000_000_007n;
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v, w] of roads) {
        adj[u].push([v, w]);
        adj[v].push([u, w]);
    }
    const dist = new Array(n).fill(Infinity);
    const ways = new Array(n).fill(0n);
    dist[0] = 0;
    ways[0] = 1n;
 
    // simple priority queue using sort (n <= 200, edges <= ~20000)
    const heap = [[0, 0]];
    const popMin = () => {
        let mi = 0;
        for (let i = 1; i < heap.length; i++) if (heap[i][0] < heap[mi][0]) mi = i;
        return heap.splice(mi, 1)[0];
    };
 
    while (heap.length) {
        const [d, u] = popMin();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u]) {
            const nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                ways[v] = ways[u];
                heap.push([nd, v]);
            } else if (nd === dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return Number(ways[n - 1]);
}

Complexity#

For n = 200, this is about 40000 * log 200 ~ 3 * 10^5 operations.

Common Mistakes#

• Forgetting to overwrite ways[v] on a strict improvement. A common bug is doing ways[v] += ways[u] for both branches; the strict-better case must reset, not accumulate, because the previous count belonged to longer paths that no longer matter.
• Not modding ways[v]. With path counts up to exponential in n, missing the modulo overflow corrupts the answer silently.
• Using a 32-bit type for distances. Edge weights up to 10^9 summed across 200 nodes overflow int32. Use int64 / long.
• Skipping the stale-pop guard if d > dist[u]: continue. Without it, you may relax outdated heap entries and double-count.
• Re-relaxing from already-popped nodes when the heap holds duplicates. The stale-pop check fixes this.

Interview Tips#

• Lead with: "Dijkstra finalises nodes in non-decreasing distance order. That ordering lets us treat path counts as a DP over the topological order of finalised distances."
• Justify why this works only with non-negative weights: with negatives we cannot freeze ways[u] when popped because Bellman-Ford may relax it later.
• Show the two-line extension and explain each branch separately. The clarity of explanation is what separates strong candidates here.
• Mention BFS instead of Dijkstra if all weights are equal: same template, replace heap with deque.
• For follow-ups, mention 0/1 BFS for binary weights and topological DP for DAGs as alternatives.

Follow-up Questions#

• What if there are negative weights but no negative cycles? Use Bellman-Ford. Distances iterate V - 1 times; counts must be recomputed inside the same iteration loop. SPFA is the practical variant.
• Count shortest paths in an unweighted graph? BFS layer by layer; ways[v] = sum of ways[u] for u in layer below v with edge u-v.
• Count paths of length exactly k? Different problem — matrix exponentiation on the adjacency matrix, O(n^3 log k).
• What about top-K shortest paths? Yen's algorithm or Eppstein's algorithm; counting is unrelated.

Key Takeaways#

• Dijkstra extends to shortest-path counting with a parallel ways[] array.
• Strict improvement: overwrite ways[v] = ways[u]. Equality: ways[v] += ways[u] mod (10^9 + 7).
• Correctness depends on non-negative weights so each node's count is finalised when popped.
• Complexity remains O((V + E) log V) time, O(V + E) space.
• Use long / int64 for distances when weights reach 10^9.
• Companies that ask this: Google, Amazon, Meta, Uber, Bloomberg, Stripe, Microsoft, Apple.