Problem 26.7 · Shortest PathsMedium

Number of Ways to Arrive at Destination

PatternDijkstra's Shortest Path 1D Dynamic Programming

What it teaches: Counting shortest paths during Dijkstra.

Practise it on judges as “Number of Ways to Arrive at Destination”.

The problem

Roads [u, v, time] are undirected. Return the number of different shortest-time routes from intersection 0 to n − 1, modulo 10⁹ + 7.

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

Constraints

1 ≤ n ≤ 200
1 ≤ time ≤ 10⁹

Pattern clues in the wording

→ "How many shortest paths"

These clues point to Dijkstra's Shortest Path: Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int countPaths(int n, int[][] roads) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	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]]	4
2	n = 2 roads = [[1,0,10]]	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Dijkstra with path counts · O(E log V)

Dijkstra with path counts

Time O(E log V) Space O(V + E)

dist[0] = 0, ways[0] = 1. When relaxing u → v: shorter → replace dist and ways and push; equal → add ways[u].

Approach 1

import java.util.*;

class Solution {
    public int countPaths(int n, int[][] roads) {
        final int MOD = 1_000_000_007;
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] r : roads) { adj.get(r[0]).add(new int[]{r[1], r[2]}); adj.get(r[1]).add(new int[]{r[0], r[2]}); }
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        long[] ways = new long[n];
        dist[0] = 0;
        ways[0] = 1;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, 0});
        while (!pq.isEmpty()) {
            long[] t = pq.poll();
            long d = t[0];
            int u = (int) t[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u)) {
                int v = e[0];
                long nd = d + e[1];
                if (nd < dist[v]) { dist[v] = nd; ways[v] = ways[u]; pq.offer(new long[]{nd, v}); }
                else if (nd == dist[v]) ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
        return (int) ways[n - 1];
    }
}

Verdict: Each node's count is final when it's popped.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 1 (one way)
Large weights (long)

Mistakes people make

int distances overflowing.
Counting ways from stale heap entries.

Interview

Follow-up questions

Why are ways[u] final when u is popped?

Command Palette

The problem

Approaches

Dijkstra with path counts

Edge cases and common mistakes

Follow-up questions