Number of Ways to Arrive at Destination

Number of Ways to Arrive at Destination

What is this problem about?

The Number of Ways to Arrive at Destination problem gives you a weighted undirected graph (representing roads). Find the number of shortest paths from node 0 to node n-1. This coding problem combines Dijkstra's shortest path algorithm with path counting DP — a classic dual-value graph problem.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it extends Dijkstra to count shortest paths simultaneously. The same dual-update rule used in "number of paths with max score" applies here: when a shorter path is found, reset count; when an equal-length path is found, add count. The shortest path, graph, topological sort, and dynamic programming interview pattern is the core.

Algorithmic pattern used

Dijkstra with dual-value state. Maintain dist[v] and count[v]. Initialize dist[0]=0, count[0]=1. For each neighbor u of current node v with edge weight w: if dist[v]+w < dist[u]: update dist[u]=dist[v]+w, count[u]=count[v]. If dist[v]+w == dist[u]: count[u]+=count[v]. Return count[n-1] % (10^9+7).

Example explanation

Graph: 0-1(1), 0-2(3), 1-2(2), 1-3(4), 2-3(1). n=4. Shortest path 0→3: 0→1→2→3 = 1+2+1=4. Also 0→2→3 = 3+1=4. Two paths. Dijkstra: dist=[0,1,3,4]. Counts=[1,1,1+1=2,count[1]+count[2]=1+1... wait:

• Process 0: relax 1 (dist=1,count=1), relax 2 (dist=3,count=1).
• Process 1 (dist=1): relax 2 (via 1: 1+2=3 == dist[2]=3 → count[2]+=count[1]→2), relax 3 (dist[3]=1+4=5).
• Process 2 (dist=3): relax 3 (3+1=4 < 5 → dist[3]=4, count[3]=count[2]=2). Answer = 2.

Common mistakes candidates make

• Forgetting modular arithmetic on count updates.
• Only running Dijkstra without tracking path counts.
• Applying the wrong update rule (reset instead of add when equal distance found).
• Using BFS instead of Dijkstra for weighted graphs.

Interview preparation tip

Dijkstra + path counting is a fundamental combination. The dual-update rule is: if shorter: replace dist and count; if equal: add to count. This pattern directly extends to "count shortest paths" in any weighted graph. Practice this combination problem, then extend to "count paths with bounded total weight." Being fluent in Dijkstra with augmented state is a strong signal in graph-heavy interviews at Meta and Google.