Number of ways to Arrive at Destination

Link : Number of ways to Arrive at Destination

Problem Statement

You are given:

• An integer n, representing intersections numbered from 0 to n - 1.

• A list roads, where each entry is [u, v, t] indicating a bidirectional road between u and v taking time t.

• You want to travel from intersection 0 to intersection n - 1.

Objective: Determine the number of distinct shortest-time paths from 0 to n - 1, modulo 10^9 + 7.

Key Insight

1. Compute the shortest travel time from node 0 to every other node using Dijkstra’s algorithm.

2. Simultaneously maintain a count of shortest paths to each node:

   • reset the path count when a strictly shorter path is found,

   • add to the existing path count when an equally short path is found.

3. Return the path count for node n - 1 modulo 10^9 + 7.

This modified Dijkstra approach is explained in multiple sources

Algorithm Outline

• Build adjacency list from roads.

• Initialize:

  • dist[node] = ∞ for all nodes except 0 = 0.

  • ways[node] = 0 for all nodes except 0 = 1.

• Use a min-heap (priority queue) ordered by current shortest-known distance.

• Extract nodes in increasing distance order. For each neighbor:

  • Compute newDist = currentDist + edgeTime.

  • If newDist < dist[neighbor]: update

    • dist[neighbor] = newDist

    • ways[neighbor] = ways[current]

    • Push neighbor into the heap.

  • Else if newDist == dist[neighbor]: increment

    • ways[neighbor] = (ways[neighbor] + ways[current]) % MOD.

Java Code

class Solution {
    static final int MOD = 1_000_000_007;

    public int countPaths(int n, int[][] roads) {
        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);
        dist[0] = 0;

        long[] ways = new long[n];
        ways[0] = 1;

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, 0});  // {time, node}

        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long time = top[0];
            int u = (int) top[1];
            if (time > dist[u]) continue;

            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                long w = edge[1];
                long newTime = time + w;

                if (newTime < dist[v]) {
                    dist[v] = newTime;
                    ways[v] = ways[u];
                    pq.offer(new long[]{newTime, v});
                } else if (newTime == dist[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }

        return (int) ways[n - 1];
    }
}

Example / Dry Run

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]
]

• Shortest travel time from 0 to 6 = 7.

• The four shortest paths are:

  • 0 → 6

  • 0 → 4 → 6

  • 0 → 1 → 2 → 5 → 6

  • 0 → 1 → 3 → 5 → 6

• The algorithm sets ways[6] = 4.

Complexity Analysis

• V = n and E = roads.length

• Modulo taken at each aggregation prevents overflow.

Why This Approach Works

• Dijkstra efficiently finds shortest distances in non-negative weighted graphs.

• By maintaining ways[], we count distinct shortest paths:

  • Upon encountering an equal-distance update, we add the count.

• Using a priority queue ensures the time complexity remains efficient even when tracking multiple path counts.

Quick Summary

• Use Dijkstra’s algorithm modified to count paths.

• Maintain a parallel array for path counts, updating on equal-distance discoveries.

• This yields both the shortest distance and the number of distinct shortest paths.