Number of Ways to Arrive at Destination
Last Updated: April 2, 2026
Understanding the Problem
We have a weighted undirected graph and need to find two things: the shortest path distance from node 0 to node n-1, and the number of distinct shortest paths that achieve that distance.
This is a classic extension of Dijkstra's algorithm. Standard Dijkstra finds the shortest distance, but here we also need to count how many different paths produce that same shortest distance. The trick is to maintain a count array alongside the distance array. When we find a shorter path to a node, we reset its count. When we find another path with the same shortest distance, we add to the count.
The key observation: whenever Dijkstra relaxes an edge and finds a new shortest distance to some node, we know the count of shortest paths to that node is exactly the count of the node we came from. And if we find an equally short path through a different node, we add that node's count to the running total.
Key Constraints:
1 <= n <= 200→ The graph has at most 200 nodes. This is small enough for O(n^2) or O(n^2 log n) approaches. Even Floyd-Warshall at O(n^3) would be 8 million operations, perfectly fine.n - 1 <= roads.length <= n * (n - 1) / 2→ The graph is connected (at least n-1 edges) and can be dense (up to ~20,000 edges for n=200).1 <= time_i <= 10^9→ Edge weights can be very large, so the total shortest path distance can exceed the int range. We need long/64-bit integers for distance tracking.modulo 10^9 + 7→ The number of paths can be astronomically large, so we take the count modulo a prime.
Approach 1: DFS Enumerate All Paths (Brute Force)
Intuition
The most direct approach: find all possible paths from node 0 to node n-1, compute each path's total weight, find the minimum weight among all paths, and count how many paths have that minimum weight.
We can enumerate paths using DFS. Starting from node 0, we explore every possible route to node n-1, tracking the accumulated distance. After exploring all paths, we know the shortest distance and can count how many paths match it.
This is correct but wildly inefficient. The number of simple paths in a graph can be exponential (factorial in the worst case for dense graphs). With n up to 200, this is completely impractical.
Algorithm
- Build an adjacency list from the roads array.
- Run DFS from node 0, tracking visited nodes to avoid cycles and accumulating path weight.
- When reaching node n-1, record the total weight.
- After exploring all paths, find the minimum weight and count paths with that weight.
- Return the count modulo 10^9 + 7.
Example Walkthrough
Code
- Time Complexity: O(n!) in the worst case. In a complete graph with n nodes, the number of simple paths can be factorial. Even with pruning, worst-case behavior is exponential.
- Space Complexity: O(n). The recursion stack and visited array both use O(n) space.
We are enumerating every possible path, which is exponentially slow. Many subpaths are shared between routes but get recomputed. What if we computed the shortest distance to each node just once and counted the shortest paths incrementally?
Approach 2: Dijkstra's Algorithm with Path Counting (Optimal)
Intuition
Here is the core insight: Dijkstra's algorithm already processes nodes in order of their shortest distance from the source. When we pop a node from the priority queue, we know its final shortest distance. So we can piggyback a counting mechanism on top of Dijkstra.
We maintain two arrays: dist[i] for the shortest distance from node 0 to node i, and ways[i] for the number of shortest paths from node 0 to node i. Initially, dist[0] = 0 and ways[0] = 1 (there is exactly one way to be at the start: you are already there).
When we relax an edge from node u to node v with weight w, three things can happen:
- Found a shorter path:
dist[u] + w < dist[v]. We updatedist[v]and setways[v] = ways[u], because all previous paths to v are no longer shortest, and the only shortest paths to v now come through u. - Found an equally short path:
dist[u] + w == dist[v]. We addways[u]toways[v], because we discovered additional shortest paths that go through u. - Found a longer path:
dist[u] + w > dist[v]. We ignore it completely.
Dijkstra's algorithm processes nodes in order of increasing distance. When node u is popped from the heap, dist[u] is finalized, and so is ways[u]. Every shortest path to u has already been discovered, because any path through an unprocessed node would have a distance at least as large as dist[u].
So when we relax edges from u, we can safely use ways[u] as the final count. If we discover a new shortest path to v (shorter than what we had before), we know the only way to achieve that distance is through u, so ways[v] = ways[u]. If the distance matches, we know there are additional shortest paths through u, so we add ways[u] to the existing count.
Algorithm
- Build an adjacency list from the roads array.
- Initialize
distarray with infinity andwaysarray with 0. Setdist[0] = 0andways[0] = 1. - Push
(0, 0)(distance, node) into a min-heap. - While the heap is not empty:
a. Pop the node with the smallest distance. Call it (d, u).
b. If d > dist[u], skip (stale entry).
c. For each neighbor v with edge weight w:
- If
dist[u] + w < dist[v]: updatedist[v] = dist[u] + w, setways[v] = ways[u], push to heap. - If
dist[u] + w == dist[v]: addways[u]toways[v](modulo 10^9+7).
- Return
ways[n-1].
Example Walkthrough
Code
- Time Complexity: O(E log V), where V = n and E = roads.length. Each edge is relaxed at most once per direction (2E total). Each heap operation is O(log V). With V up to 200 and E up to ~20,000, this runs in roughly 160,000 operations.
- Space Complexity: O(V + E). The adjacency list stores O(E) edges. The dist and ways arrays use O(V) space. The heap holds at most O(E) entries.