Number of ways to arrive at destination
HardDijkstra that also counts shortest routes
Problem
Count the number of shortest paths from node 0 to node n-1 in a weighted graph, modulo 1e9+7.
Run Dijkstra but also count paths: shorter resets the count, equal-length adds to it.
The idea
Run Dijkstra as usual but carry a second array ways[]. When you find a strictly shorter route to v, v inherits u's count. When you find an equally short route, add u's count to v's. The animation shows the shortest-distance backbone; ways[n-1] mod 1e9+7 is the final answer.
Step 1 of 13. Goal: the shortest distance from A to every other node. Start A = 0, everyone else = ∞ (unknown). dist [0, ∞, ∞, ∞, ∞], settled —.
1dist[0] = 0, ways[0] = 1, all others dist = ∞2min-heap H = {(0, 0)}3while H not empty:4 (d, u) = pop-smallest from H5 for each edge (u → v, weight w):6 if d + w < dist[v]: // strictly shorter route7 dist[v] = d + w; ways[v] = ways[u]; push (dist[v], v)8 else if d + w == dist[v]: ways[v] += ways[u]Input
- nodes
- 5, 6 edges
Memory
- dist
- [0, ∞, ∞, ∞, ∞]
- frontier
- —
Output
- settled
- —
- shortest dist
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- 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
- Explanation:
- 4 different shortest routes reach node 6.
Example 2
- Input:
- n = 2, roads = [[0,1,1]]
- Output:
- 1
- Explanation:
- One road → 1 way.
Example 3
- Input:
- n = 3, roads = [[0,1,1],[0,2,1],[1,2,0]]
- Output:
- 2
- Explanation:
- Ties create multiple shortest ways.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.