Number of Ways to Arrive at Destination
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 an 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. We 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.
Whenever Dijkstra relaxes an edge and finds a new shortest distance to some node, the count of shortest paths to that node equals the count of the node we came from. 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, small enough that even an O(n^3) approach would finish in time.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→ A path can have up to 199 edges, so the total distance can reach roughly 2 x 10^11, which overflows a 32-bit int. Distances must use 64-bit integers.modulo 10^9 + 7→ The path count can grow large, so we take it modulo a prime.
Approach 1: DFS Enumerate All Paths (Brute Force)
Intuition
Find all possible paths from node 0 to node n-1, compute each path's total weight, find the minimum weight, and count how many paths have that minimum weight.
We enumerate paths using DFS. Starting from node 0, we explore every 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.
Enumerating every path is exponentially slow, and shared subpaths get recomputed across routes. The next approach computes the shortest distance to each node once and accumulates the path counts during a single graph traversal.
Approach 2: Dijkstra's Algorithm with Path Counting (Optimal)
Intuition
Dijkstra's algorithm processes nodes in order of their shortest distance from the source. When we pop a node from the priority queue, its final shortest distance is fixed. We can attach a counting mechanism on top of that.
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, since there is one path from the start to itself, the empty path.
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.
The argument rests on the order in which Dijkstra finalizes nodes. When node u is popped from the heap, dist[u] is final: any path reaching u through a node still in the heap would have distance at least dist[u], so no shorter path to u remains. Because every shortest path to u arrives through some neighbor that was popped earlier, and each of those neighbors already relaxed its edge into u, ways[u] has accumulated the counts of all of them. So ways[u] is also final at pop time.
This is why using ways[u] during relaxation is safe. A strictly shorter path to v discards v's old paths and replaces them with the paths through u, so ways[v] = ways[u]. An equal-distance path adds a new set of shortest paths through u, so ways[v] += ways[u]. One requirement: edge weights are positive (time_i >= 1), which guarantees u is finalized before any node it relaxes, so no count is read before it is complete.
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:
- Pop the node with the smallest distance. Call it
(d, u). - If
d > dist[u], skip (stale entry). - 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.