Number of Ways to Arrive at Destination | Leetcode 1976 | Simple Dijkstra + Path-Counting Guide in Python

Learn how to solve Number of Ways to Arrive at Destination with Dijkstra’s algorithm while counting paths. Clear intuition, commented Python code, dry run, and Big-O analysis.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

You are given:

• n cities numbered 0 … n-1,
• a list of bidirectional roads u ↔ v with travel time w.

Start at city 0 and finish at city n − 1.

1. Find the shortest possible travel time.
2. Return how many different shortest routes exist, mod 1 000 000 007.
   (Two routes are different if the sequence of visited cities differs at any step.)

2. Example

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]
]

Shortest time: 7
Number of different shortest paths: 6

3. Intuition & approach

3.1 Dijkstra finds the time

Classic Dijkstra’s algorithm gives the minimum travel time from city 0 to every other city because all edge weights (w) are non-negative.

3.2 Counting paths on the fly

While Dijkstra explores the graph we also maintain:

• ways[i] – how many shortest paths reach city i.

Rules when we process an edge node → adjNode with weight weight:

Because Dijkstra processes nodes by increasing distance, when we pop a node its recorded distance is already the true shortest, so the counting is safe.

4. Python code

import sys
import heapq
from typing import List


class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10**9 + 7

        # 1️⃣ build undirected adjacency list
        adj_list = [[] for _ in range(n)]
        for u, v, w in roads:
            adj_list[u].append([v, w])
            adj_list[v].append([u, w])

        # 2️⃣ distance & ways arrays
        distance = [sys.maxsize for _ in range(n)]
        ways     = [0 for _ in range(n)]
        distance[0] = 0        # start city
        ways[0]     = 1        # one trivial path to itself

        # 3️⃣ min-heap for Dijkstra (dist, node)
        priority_queue = [[0, 0]]

        while priority_queue:
            dist, node = heapq.heappop(priority_queue)

            # Skip stale entries
            if dist != distance[node]:
                continue

            # 4️⃣ relax edges
            for adjNode, weight in adj_list[node]:
                new_dist = dist + weight

                if new_dist < distance[adjNode]:
                    # found a strictly better time
                    distance[adjNode] = new_dist
                    heapq.heappush(priority_queue, [new_dist, adjNode])
                    ways[adjNode] = ways[node]              # reset count

                elif new_dist == distance[adjNode]:
                    # found another shortest route
                    ways[adjNode] = (ways[adjNode] + ways[node]) % MOD

        return ways[n - 1] % MOD

5. Step-by-step explanation

1. Adjacency list – every road stored twice since travel is two-way.
2. Arrays
   • distance[i] = best travel time seen so far to city i.
   • ways[i] = number of shortest-time routes to city i.
3. Heap pop – always gives us the city with the smallest current time.
4. Edge relaxation – update both distance and ways according to the table above.
5. Answer – after heap empties, ways[n-1] is the required count.

6. Dry run (mini graph)

0 --1--> 1
0 --1--> 2
1 --1--> 3
2 --1--> 3

Two different shortest routes: 0-1-3 and 0-2-3.

7. Complexity

V = n, E = len(roads).

8. Conclusion

• Using Dijkstra while carrying a ways counter lets us solve Number of Ways to Arrive at Destination in one pass.
• Update rules: reset on a better distance, add on an equal distance.
• Always take results mod 1 000 000 007 to prevent overflow.

With these steps you can confidently compute both the fastest time and the exact count of fastest routes between two cities.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.