← DSA Atlas
Dedicated problem page · #1976

Number of Ways to Arrive at Destination

MediumShortest Path, Dijkstra and Minimum Spanning TreeDijkstra + shortest-path countingMin-heap Dijkstra with a ways[] DP accumulator
Solve on LeetCode ↗
1976
MediumShortest Path, Dijkstra and Minimum Spanning TreeMin-heap Dijkstra with a ways[] DP accumulatorDijkstra + shortest-path counting

Number of Ways to Arrive at Destination

There are n intersections labeled 0..n-1 connected by bidirectional roads, where roads[i] = [u, v, time] takes the given time to travel. Starting at intersection 0, return the number of different ways to reach intersection n-1 in the shortest possible time, modulo 10^9 + 7.

Open official problem prompt ↗
In plain English

Count how many distinct fastest routes exist from intersection 0 to intersection n-1.

Picture it like this

A GPS not only reports the quickest driving time but tallies how many different quickest routes tie for first place.

Example
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
Why
The shortest time from 0 to 6 is 7, and exactly 4 distinct routes achieve it (including the direct road 0->6).
Constraints
1 <= n <= 200n - 1 <= roads.length <= n*(n-1)/2roads[i].length == 30 <= u, v <= n - 1, u != v1 <= time <= 10^9There is at most one road between any two intersectionsYou can reach any intersection from any other intersection
Pattern lesson

See the pattern, then code

Dijkstra + shortest-path counting
Recognition clue

You need both the shortest travel time and how many shortest routes achieve it on a non-negative weighted graph - Dijkstra augmented with a path-count array.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. Run Dijkstra for shortest times, but also carry ways[v]: when you find a strictly shorter time to v, copy the count from the node that reached it; when you find an equal-time route, add that node's count.

New words, made simpleKnow these before the algorithm
Shortest-path count
The number of distinct paths whose total weight equals the minimum distance.
ways[] accumulator
A DP array counting shortest routes to each node, updated during relaxation.
Stale heap entry
A popped (time,node) pair whose time is worse than the node's already-finalized dist; it must be ignored.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Enumerate all paths then filter

Infeasible; the number of paths explodes.

List every path from 0 to n-1 and keep those of minimum length.

Time ExponentialSpace O(V)
Best choiceDijkstra + count DP

Optimal: one Dijkstra pass yields both shortest time and the count.

Standard Dijkstra for distances, propagating and summing route counts on strict-improve and tie events.

Time O(E log V)Space O(V + E)
The rule we keep true

Invariant

When a node is finalized (popped with time == dist), ways[node] holds the total number of shortest paths from the source to it, taken modulo 10^9+7.

Why this is correct

Reasoning

Dijkstra finalizes nodes in non-decreasing distance order, so every predecessor on a shortest path to v is finalized before v is. Thus ways[v] correctly sums the counts of all predecessors u with dist[u] + w = dist[v]: a strict improvement resets the count to that predecessor's, and each equal-distance predecessor adds its share.

The algorithm in three movesSay these aloud before coding
1Build an adjacency list and arrays dist (min time, infinity) and ways (0), with dist[0]=0 and ways[0]=1

dist[0]=0, ways[0]=1

2Pop the smallest-time node; skip if it is stale (popped time > dist[node])

dist[6]=7 via 0 directly, ways[6]=1

3Relax each neighbor: if new time < dist[neighbor], set dist and ways[neighbor]=ways[node] and push

equal-time routes via node 5 add in

4If new time == dist[neighbor], add ways[node] to ways[neighbor] modulo 10^9+7

ways[6]=4 -> return 4

5Return ways[n-1] mod 10^9+7

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
22
33
44
55
66
1 · Readsource 0
2 · Askseed
3 · Update statedist[0]=0, ways[0]=1
4 · ResultPush (0,0).
Key takeaway

Dijkstra settles shortest times while ways[] accumulates the number of shortest routes reaching each node.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-9Graph and DP arrays

    Undirected adjacency plus dist (infinity) and ways (0); source seeded with dist 0 and one way.

  2. 2
    Lines 13-15Stale skip

    If the popped time exceeds dist[u], a better time was already finalized, so ignore this entry.

  3. 3
    Lines 16-20Strict improvement

    A shorter time resets ways[v] to ways[u] and pushes the new distance.

  4. 4
    Lines 21-22Tie accumulation

    An equal-time route adds ways[u] into ways[v] modulo 10^9+7 without pushing again.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • n == 1 means source is destination, answer 1
  • Edge times up to 10^9 mean path sums can exceed 32-bit range; Python ints handle it
  • Multiple tie routes require the modulo to keep counts bounded
!

Common beginner mistakes

  • Applying the modulo only at the end - apply it on each tie addition to avoid overflow in other languages
  • Adding to ways on a strict improvement instead of overwriting it
  • Not skipping stale heap entries, which can double-count routes
Check your understanding

Why is it safe to overwrite ways[v] on a strict improvement but add on a tie?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)