Number of Ways to Arrive at Destination: Dijkstra Meets DP
Count the shortest paths in a weighted graph by fusing Dijkstra with DP path counting — intuition, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most shortest-path problems ask a single question: how fast can I get there? This one asks a sneakier follow-up: how many different fastest routes exist? You're not just running Dijkstra — you're running it while keeping a tally of ties.
The twist is that a plain shortest-path algorithm throws away exactly the information you need. The moment it locks in a distance, it forgets how many ways produced that distance. The fix is small but precise: carry a second array alongside the distance array, and update both under carefully chosen conditions.
Get those conditions right and the whole thing collapses into one Dijkstra pass. Get them wrong — off by one comparison — and your count is silently, unrecoverably incorrect.
The problem
You're in a city with n intersections numbered 0 to n - 1, connected by bi-directional roads. Each road is [u, v, time] — it takes time minutes to travel between u and v. Return the number of distinct ways to travel from intersection 0 to intersection n - 1 in the shortest possible time. Because the answer can be huge, return it modulo 10^9 + 7.
Input: n = 3, roads = [[0,1,1], [1,2,1], [0,2,2]]
Output: 2
// Shortest time from 0 to 2 is 2 minutes.
// Route A: 0 -> 2 (2 minutes, direct)
// Route B: 0 -> 1 -> 2 (1 + 1 = 2 minutes)
// Both hit the minimum, so the answer is 2.Two words in that statement carry all the weight: distinct and shortest. A route only counts if its total time equals the minimum. A route that reaches the destination in 3 minutes when the record is 2 contributes nothing.
The brute force baseline
The naive instinct is to enumerate every path from 0 to n - 1, measure each one, find the minimum time, then count how many paths tie for it — a depth-first search over all routes.
function countPathsBrute(n, roads) {
const graph = Array.from({ length: n }, () => []);
for (const [u, v, w] of roads) {
graph[u].push([v, w]);
graph[v].push([u, w]);
}
let best = Infinity, ways = 0;
function dfs(node, time, seen) {
if (time > best) return; // prune hopeless routes
if (node === n - 1) {
if (time < best) { best = time; ways = 1; }
else if (time === best) ways++;
return;
}
for (const [next, w] of graph[node]) {
if (!seen.has(next)) {
seen.add(next);
dfs(next, time + w, seen);
seen.delete(next);
}
}
}
dfs(0, 0, new Set([0]));
return ways;
}This is correct but hopeless at scale. The number of simple paths in a dense graph is exponential — a graph with a few dozen well-connected intersections can hold billions of routes. You'd re-walk the same prefixes over and over, learning nothing between visits. For n up to 200, this times out immediately.
The key insight: count while you relax
Dijkstra already finds the minimum time to every node. The idea is to piggyback a path count onto that same machinery, using dynamic programming.
Keep two arrays:
minW[v]— the shortest time discovered so far to reach nodev.pathCount[v]— how many distinct shortest routes reachvin exactlyminW[v]time.
When you pop node u off the priority queue and look at an edge u -> v of weight w, one of three things is true about the candidate time newW = minW[u] + w:
| Case | Condition | What it means | Action |
|---|---|---|---|
| Strictly better | newW < minW[v] | You found a faster route to v. Every old route to v is now obsolete. | minW[v] = newW; reset pathCount[v] = pathCount[u] |
| Tie | newW === minW[v] | Another route reaches v in the same record time. | Add: pathCount[v] += pathCount[u] |
| Worse | newW > minW[v] | This route is slower. Ignore it. | do nothing |
The additive principle of counting drives the tie case: if there are pathCount[u] ways to optimally reach u, then every one of them extends into a distinct optimal route to v. So v inherits u's count on top of whatever it already had.
That "reset vs. add" distinction is the entire problem. Reset when you beat the record; accumulate when you match it.
The optimal solution
This mirrors the algorithm in the interactive visualizer exactly — a min-priority queue keyed on arrival time, two parallel arrays, and the three-way comparison inside the relaxation loop.
var countPaths = function(n, roads) {
let graph = Array.from({ length: n }, () => []);
for (let [u, v, w] of roads) {
graph[u].push([v, w]);
graph[v].push([u, w]);
}
let pq = new MinPriorityQueue(x => x[0]); // order by arrival time
let minW = new Array(n).fill(Infinity);
let pathCount = new Array(n).fill(0);
pq.push([0, 0]); // [time, node]
minW[0] = 0;
pathCount[0] = 1; // one trivial way to be at the source
while (!pq.isEmpty()) {
let [currW, curr] = pq.pop();
for (let [neighbor, neighborW] of graph[curr]) {
let newW = currW + neighborW;
if (newW < minW[neighbor]) {
minW[neighbor] = newW;
pq.push([newW, neighbor]);
pathCount[neighbor] = pathCount[curr]; // reset
} else if (newW === minW[neighbor]) {
pathCount[neighbor] =
(pathCount[curr] + pathCount[neighbor]) % (1e9 + 7); // add
}
}
}
return pathCount[n - 1];
};Two details make this correct. First, pathCount[0] = 1 seeds the recurrence — the source has exactly one trivial "path" (standing still). Second, the modulo lives only in the tie branch, because that's the only place counts grow by addition. The reset branch just copies an already-reduced value, so it needs no modulo of its own.
Walkthrough
Trace n = 3, roads = [[0,1,1], [1,2,1], [0,2,2]]. The adjacency list is 0: [(1,1),(2,2)], 1: [(0,1),(2,1)], 2: [(1,1),(0,2)]. We start with minW = [0, ∞, ∞], pathCount = [1, 0, 0], and the queue holding [0, 0].
| Pop | Edge examined | newW | vs minW[v] | Case | minW after | pathCount after |
|---|---|---|---|---|---|---|
[0,0] | 0→1 (w=1) | 1 | 1 < ∞ | better | [0,1,∞] | [1,1,0] |
[0,0] | 0→2 (w=2) | 2 | 2 < ∞ | better | [0,1,2] | [1,1,1] |
[1,1] | 1→0 (w=1) | 2 | 2 > 0 | worse | [0,1,2] | [1,1,1] |
[1,1] | 1→2 (w=1) | 2 | 2 === 2 | tie (!) | [0,1,2] | [1,1,2] |
[2,2] | 2→1 (w=1) | 3 | 3 > 1 | worse | [0,1,2] | [1,1,2] |
[2,2] | 2→0 (w=2) | 4 | 4 > 0 | worse | [0,1,2] | [1,1,2] |
The decisive row is 1→2. Node 2 already had time 2 from the direct road, giving it pathCount = 1. Reaching it again through node 1 also costs 2 — a tie — so node 2 absorbs node 1's single path, and its count climbs to 2. Every later edge is strictly slower and changes nothing. The answer is pathCount[2] = 2.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(E log V) | Dijkstra with a binary-heap priority queue: each of the E edges triggers at most one push, and each pop/push costs log V |
| Space | O(V + E) | Adjacency list holds every edge; the minW, pathCount, and queue arrays are each O(V) |
Counting adds no asymptotic cost. The pathCount array is one extra O(V) allocation and the tie-check is O(1) per edge, so the whole thing runs at the same order as vanilla Dijkstra. That's the payoff of fusing the DP into the relaxation step instead of enumerating paths separately.
Common mistakes
- Using
<=instead of two separate branches. Collapsing "better" and "tie" into onenewW <= minW[v]block loses the distinction. A strictly-better route must reset the count; a tie must add. One comparison operator cannot do both. - Forgetting the modulo, or putting it in the wrong branch. Counts explode past
2^53on large graphs. Apply% (1e9 + 7)in the additive (tie) branch. Skipping it gives wrong answers on big inputs; JavaScript won't warn you. - Seeding
pathCount[0] = 0. If the source starts with zero paths, every count stays zero forever — the recurrence multiplies nothing. It must be1. - Not skipping stale queue entries. Because Dijkstra can push a node multiple times, a robust version ignores a popped entry whose time already exceeds
minW[node]. Re-processing a stale, longer entry can inflate the tie count incorrectly. - Treating roads as one-directional. The graph is undirected — every road must be added to both
graph[u]andgraph[v], or you'll miss valid routes.
Where this pattern shows up next
Weighted-graph traversal with a priority queue and per-node bookkeeping is a family, not a one-off:
- Network Delay Time — the purest Dijkstra: propagate a signal and find the last node to hear it.
- Shortest Path in Binary Matrix — BFS as unit-weight Dijkstra on an implicit grid graph.
- Course Schedule II — topological ordering, the DAG cousin of "process nodes in the right order."
- Redundant Connection — union-find over an undirected graph to spot the edge that closes a cycle.
You can also step through the algorithm in the visualizer to watch minW and pathCount update side by side as each edge relaxes.
FAQ
Why does this problem need two arrays instead of one?
Standard Dijkstra tracks only the shortest distance to each node, which answers "how fast" but discards "how many." The second array, pathCount, remembers how many distinct routes achieve that shortest distance. They update together during relaxation: when a node's shortest time improves, its count resets to the incoming node's count; when a new route ties the current best, the counts add. One array alone can't hold both the record and the tally.
When do I reset the count versus add to it?
Reset when you find a strictly faster route (newW < minW[v]): the old routes are now too slow to matter, so v takes on the count of the node you arrived from. Add when you find an equal-time route (newW === minW[v]): both the existing routes and the new ones are optimal, so you accumulate pathCount[v] += pathCount[u]. Slower routes (newW > minW[v]) are ignored entirely. Mixing up reset and add is the single most common bug in this problem.
Why is the answer taken modulo 10^9 + 7?
The number of shortest paths grows combinatorially — a graph with many parallel equal-length segments can produce counts far larger than a 64-bit integer, let alone JavaScript's safe integer limit of about 9 quadrillion. Returning the result modulo 10^9 + 7 keeps every intermediate count bounded while preserving the exact answer under modular arithmetic. Apply the modulo in the additive branch, where counts actually grow.
What is the time complexity of the Dijkstra plus DP approach?
O(E log V), identical to ordinary Dijkstra with a binary-heap priority queue, where E is the number of roads and V is the number of intersections. Each edge is relaxed at most once and each heap operation costs O(log V). The path-counting logic adds only an O(1) comparison per edge and one extra O(V) array, so it contributes nothing to the asymptotic cost. Space is O(V + E) for the adjacency list and the two tracking arrays.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.