☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Number of ways to arrive at destination

Hard TUF ID 524 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A city has n intersections numbered 0 to n - 1 and a list of two-way roads [u, v, time]. Every intersection can be reached from every other one, and there is at most one road between any pair. Return the number of different routes from intersection 0 to intersection n - 1 that take the shortest possible time. The count can be huge, so return it modulo 10^9 + 7.

Constraints (LeetCode 1976): 1 ≤ n ≤ 200, 1 ≤ time ≤ 10^9, n - 1 ≤ roads.length ≤ n(n-1)/2.

Example 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]]
answer = 4          // shortest time is 7: 0-6, 0-4-6, 0-1-2-5-6, 0-1-3-5-6

Example 2

n = 2, roads = [[1,0,10]]
answer = 1          // the only road is the only route

Two routes are different if they use a different sequence of roads. Since every road takes positive time, a shortest route never visits the same intersection twice, so we are counting simple paths of minimum total time.

Approach 1: Brute force

Intuition. Enumerate every simple path from 0 to n - 1 with a depth-first search, carrying the elapsed time. Keep two numbers: the best time seen so far and how many paths achieve it. A faster path resets the count to 1, an equal path increments it. One easy prune: if the current partial path is already slower than the best complete path, no extension can help, because times only grow.

Algorithm.

  1. Mark 0 as on the path and start the DFS at time 0.
  2. At node u: if time > best, return. If u is the target, update best and the count, then return.
  3. Otherwise recurse into every neighbour not on the current path, unmarking it afterwards.
  4. Return the count modulo 10^9 + 7.
static int bruteForce(int n, int[][] roads) {
    List<List<int[]>> adj = buildGraph(n, roads);
    long[] best = {Long.MAX_VALUE, 0};               // {shortest time so far, routes with that time}
    boolean[] onPath = new boolean[n];
    onPath[0] = true;
    explore(adj, 0, n - 1, 0, onPath, best);
    return (int) (best[1] % MOD);
}

static void explore(List<List<int[]>> adj, int u, int target, long time, boolean[] onPath, long[] best) {
    if (time > best[0]) return;                      // already slower than a known route
    if (u == target) {
        if (time < best[0]) {
            best[0] = time;
            best[1] = 1;
        } else {
            best[1]++;
        }
        return;
    }
    for (int[] e : adj.get(u)) {
        int v = e[0];
        if (onPath[v]) continue;                     // positive times: a shortest route never repeats a node
        onPath[v] = true;
        explore(adj, v, target, time + e[1], onPath, best);
        onPath[v] = false;
    }
}

Complexity. Time is exponential: a dense graph has on the order of (n - 2)! simple paths between two nodes, and the prune does not change that in the worst case. Space O(n) for the recursion and the path markers. Useful only to check the faster methods on tiny inputs.

Approach 2: Better, distances first, then count on the shortest-path DAG

Intuition. Split the question in two. First compute dist[v], the shortest time from 0 to every node, with Dijkstra. Then notice which roads can appear on a shortest route: a directed use u → v lies on some shortest route exactly when dist[u] + time == dist[v]. These “tight” edges form a directed acyclic graph, because along any tight edge the distance strictly increases (times are at least 1).

Every shortest route to v is a shortest route to some tight predecessor u, followed by the edge u → v. So ways[v] is the sum of ways[u] over tight predecessors. If we process nodes in increasing order of dist, every predecessor is finished before we use it, and the sum is complete.

Algorithm.

  1. Run Dijkstra from 0 to get dist.
  2. Sort the nodes by dist. Set ways[0] = 1.
  3. For each node u in that order, for each road u - v: if dist[u] + time == dist[v], add ways[u] to ways[v] modulo 10^9 + 7.
  4. Return ways[n - 1].
static int twoPass(int n, int[][] roads) {
    List<List<int[]>> adj = buildGraph(n, roads);
    long[] dist = shortestTimes(adj, 0);
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Long.compare(dist[a], dist[b]));
    long[] ways = new long[n];
    ways[0] = 1;
    for (int u : order) {                            // every predecessor of u is strictly closer, so it came earlier
        if (dist[u] == Long.MAX_VALUE) break;
        for (int[] e : adj.get(u)) {
            int v = e[0];
            if (dist[u] + e[1] == dist[v]) ways[v] = (ways[v] + ways[u]) % MOD;
        }
    }
    return (int) ways[n - 1];
}

static long[] shortestTimes(List<List<int[]>> adj, int src) {
    long[] dist = new long[adj.size()];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.offer(new long[]{0, src});
    while (!pq.isEmpty()) {
        long[] cur = pq.poll();
        long d = cur[0];
        int u = (int) cur[1];
        if (d > dist[u]) continue;
        for (int[] e : adj.get(u)) {
            if (d + e[1] < dist[e[0]]) {
                dist[e[0]] = d + e[1];
                pq.offer(new long[]{dist[e[0]], e[0]});
            }
        }
    }
    return dist;
}

Complexity. Time O(E log E) for Dijkstra plus O(n log n) for the sort and O(n + E) for the counting pass. Space O(n + E).

Approach 3: Optimal, Dijkstra that counts as it goes

Intuition. The two passes can be fused. Dijkstra already pops nodes in increasing order of distance, which is exactly the order the counting pass needs. When a node u is popped with its final distance, all of its tight predecessors have strictly smaller distance and were popped earlier, so ways[u] is already complete. Relaxing an edge u → v with new time nd has three outcomes:

Algorithm.

  1. dist[0] = 0, ways[0] = 1; push {0, 0}.
  2. Pop {d, u}; skip it if d > dist[u] (stale).
  3. For each road u - v with time t, let nd = d + t and apply the three cases above, pushing {nd, v} only on a strict improvement.
  4. Return ways[n - 1].
static int optimal(int n, int[][] roads) {
    List<List<int[]>> adj = buildGraph(n, roads);
    long[] dist = new long[n];
    long[] ways = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    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});                      // {time, node}
    while (!pq.isEmpty()) {
        long[] cur = pq.poll();
        long d = cur[0];
        int u = (int) cur[1];
        if (d > dist[u]) continue;                   // stale entry
        for (int[] e : adj.get(u)) {
            int v = e[0];
            long nd = d + e[1];
            if (nd < dist[v]) {                      // strictly faster: earlier routes to v are not shortest
                dist[v] = nd;
                ways[v] = ways[u];
                pq.offer(new long[]{nd, v});
            } else if (nd == dist[v]) {              // equally fast: every shortest route to u extends to v
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return (int) ways[n - 1];
}

Dry run on a diamond 0-1 (1), 0-2 (1), 1-3 (1), 2-3 (1):

pop relaxation dist ways
{0, 0} 1: 1 < ∞ replace; 2: 1 < ∞ replace [0, 1, 1, ∞] [1, 1, 1, 0]
{1, 1} 3: 2 < ∞ replace with ways[1] [0, 1, 1, 2] [1, 1, 1, 1]
{1, 2} 3: 2 == 2, add ways[2] [0, 1, 1, 2] [1, 1, 1, 2]
{2, 3} 1, 2: 3 > 1, too slow unchanged [1, 1, 1, 2]

The answer is ways[3] = 2, the two sides of the diamond.

Complexity. Time O(E log E): a standard Dijkstra with constant extra work per relaxation. Space O(n + E).

Why is double counting impossible? A node’s routes are only added when it is popped with a non-stale distance, and that happens once per node. A stale entry has d > dist[u], so even without the skip, d + t would be larger than dist[u] + t ≥ dist[v] and would fall into the “too slow” case. Pushes happen only on strict improvement, so two live entries with the same distance for the same node never exist.

Edge cases and pitfalls