Number of Ways to Reach Destination in Shortest Time

Problem Statement❯

You are in a city with n intersections (numbered from 0 to n - 1) connected by bidirectional roads. Each road connects two intersections u and v and takes time minutes to travel.

You are given:

An integer n — the number of intersections
A 2D array roads where each entry is [u, v, time]

Your goal is to determine how many different ways you can travel from intersection 0 (source) to intersection n - 1 (destination) in the shortest possible time.

Return the number of such shortest paths modulo 10⁹ + 7.

Examples❯

n	roads	Expected Output	Description
7	[[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	There are 4 different shortest paths from 0 to 6 to 5 to 3 to 1 to 2 to 5 to 6 to 0
2	[[0,1,1]]	1	Only one path from 0 to 1
4	[[0,1,1],[1,2,1],[2,3,1],[0,3,3]]	2	Two paths of equal minimum length: 0→1→2→3 and 0→3

Solution❯

This problem is a variation of the classic Dijkstra’s Algorithm, where instead of just finding the shortest distance, we also keep track of how many ways we can reach each node in that shortest time.

We maintain two arrays:

dist[i] - the shortest time to reach node i
ways[i] - the number of ways to reach node i in dist[i] time

We initialize dist[0] = 0 and ways[0] = 1 and use a priority queue to simulate Dijkstra’s traversal based on time.

At each step, if we find a shorter path to a node, we update both its distance and the number of ways to reach it. If we find another path with the same shortest distance, we add to the number of ways.

Finally, ways[n - 1] gives us the number of shortest paths to the destination node.

Algorithm Steps❯

Create an adjacency list from the roads array.
Initialize dist array to store shortest time to each node (set all to Infinity except source).
Initialize ways array to store number of ways to reach each node (set all to 0 except source).
Use a priority queue (min-heap) and start from node 0 with time 0.
While the queue is not empty:

Pop the node with minimum current time.
For each neighbor of this node:

If a new shorter time is found, update dist and set ways to the current node's ways.
If the same time is found, increment ways by current node's ways.

Return ways[n - 1] % (10⁹ + 7).

Code

JavaScript

function countPaths(n, roads) {
  const MOD = 1e9 + 7;
  const adj = Array.from({ length: n }, () => []);

  for (const [u, v, t] of roads) {
    adj[u].push([v, t]);
    adj[v].push([u, t]);
  }

  const dist = Array(n).fill(Infinity);
  const ways = Array(n).fill(0);
  const minHeap = [[0, 0]]; // [time, node]

  dist[0] = 0;
  ways[0] = 1;

  while (minHeap.length > 0) {
    minHeap.sort((a, b) => a[0] - b[0]); // simple priority queue
    const [time, node] = minHeap.shift();

    for (const [nei, t] of adj[node]) {
      const newTime = time + t;
      if (newTime < dist[nei]) {
        dist[nei] = newTime;
        ways[nei] = ways[node];
        minHeap.push([newTime, nei]);
      } else if (newTime === dist[nei]) {
        ways[nei] = (ways[nei] + ways[node]) % MOD;
      }
    }
  }

  return ways[n - 1];
}

const 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]];
console.log("Number of shortest paths from 0 to 6:", countPaths(7, roads));

⬅ Previous TopicCheapest Flights Within K Stops - Graph Problem

Next Topic ⮕Minimum Multiplications to Reach End - Graph BFS