1976. Number of Ways to Arrive at Destination
Problem Description
In this problem, you are placed in a fictional city with n
intersections, each represented by numbers ranging from 0 to (n - 1)
. The city has a series of bi-directional roads, ensuring that one can travel between any two intersections in the city, and importantly, there is no more than one direct road connecting any pair of intersections.
You are provided with two inputs: an integer n
and a 2D array of integers roads
. Each element in roads
is a sub-array that takes the form [u_i, v_i, time_i]
where u_i
and v_i
represent the intersections connected by this road, and time_i
is the time required to travel between these intersections.
The goal is to calculate the number of different ways you can travel from intersection 0 (the starting point) to intersection n - 1
(the destination), specifically taking the shortest possible time. The challenge is to figure out not just the quickest route but also how many distinct quickest routes there are. Because the number of ways can be quite large, you are required to return this number modulo 10^9 + 7
to keep the output manageable and practical for use in further computations.
Intuition
To solve this problem, we need to use a shortest path algorithm that could also count the number of shortest paths to each node. Dijkstra's Algorithm is a good fit for finding the shortest path, but it does not inherently count the paths. Hence, we must modify the standard algorithm to also keep track of the number of ways to reach each intersection within the minimum travel time.
We start by initializing an adjacency matrix g
to store the travel times between intersections, with INF
(infinity) as the default value to represent the absence of a direct route. We then populate g
with the given travel times for each road between intersections.
We maintain an array dist
to store the shortest travel time from the start (intersection 0) to every other intersection, initializing the distances to INF
and setting the distance to the start as 0, since it costs no time to stay at the start. The array w
holds the count of the shortest ways to reach each intersection; we initialize w[0]
to 1 because there is one way to start from intersection 0, i.e., doing nothing.
A boolean array vis
keeps track of whether we have visited an intersection. The core of the algorithm involves iterating through all intersections to find the non-visited intersection with the shortest distance recorded so far. Upon finding such an intersection, we mark it as visited.
For the current intersection t
, we attempt to update the shortest distance to all other non-visited intersections i
. If the distance to an intersection i
can be decreased by traveling through t
, we update the distance and set the number of ways to reach i
to the number of ways to reach t
, as a new shortest path through t
has been discovered. If we find a route to i
that is equal to its current shortest distance, it implies that there is an additional way to reach i
via t
, and hence we increment w[i]
by the number of ways w[t]
.
After updating all distances and counts of ways from intersection t
, we eventually conclude with w[n - 1]
, which holds the count of the shortest paths to the destination. This value is then returned modulo 10^9 + 7
as per the problem's requirement.
The thought process behind this approach is to ensure we accurately track the minimum travel time as well as all viable routes contributing to this minimum. We solve both parts of the problem - shortest time and the count of shortest paths - in a single unified framework by extending Dijkstra's Algorithm.
Learn more about Graph, Topological Sort, Dynamic Programming and Shortest Path patterns.
Solution Approach
The implementation of the solution begins with some initial definitions:
INF
as infinity, which represents a large value that is intended to be higher than any time that could be taken to travel between intersections.MOD
as the modulus value10^9 + 7
for the final result.
The graph g
is initialized as a two-dimensional array of size n x n
, filled with INF
to represent that initially there are no connections between intersections. We then iterate through the input roads
, where each road
is given as [u, v, t]
. Here, u
and v
represent the intersections, and t
is the time taken to go between them. This data populates the matrix with the appropriate travel times, ensuring that g[u][v]
and g[v][u]
are set to t
to reflect the bi-directionality of the roads.
Next, we have the dist
array, where dist[i]
represents the current known shortest time to reach intersection i
from the origin (intersection 0), which is set to INF
for all intersections except the origin, for which dist[0]
is 0.
The w
array, where w[i]
represents the total number of the shortest paths to intersection i
, is initialized to 0 for all intersections except w[0]
, which is set to 1 since there is exactly one way to be at the start - to do nothing.
The vis
array is a boolean array that tracks whether or not an intersection has been visited.
The core logic involves a loop that runs for n
iterations. Each iteration selects the intersection t
that has not been visited yet and has the smallest value in dist
. This intersection is then marked as visited.
After selecting an intersection t
, another loop runs through all intersections i
. If we have already visited i
or if i
is t
, we skip the current iteration. Otherwise, we sum dist[t]
and g[t][i]
to find a new possible shortest distance ne
to i
via t
.
If ne
is smaller than the current dist[i]
, it means we've found a shorter path to i
via t
, so we update dist[i]
with this new shortest distance and set w[i]
to w[t]
to reflect the number of shortest paths to i
.
In the scenario where ne
is equal to the current dist[i]
, it means we have found an alternative shortest path to i
via t
. Therefore, we add the number of ways to get to t
(w[t]
) to the current number of ways to get to i
(w[i]
).
This process continues until all intersections are visited. The algorithm ensures that the shortest time and the count of possible shortest paths have been calculated by the time the loop ends.
The final result is given by w[n - 1]
, which holds the total number of shortest paths to n - 1
i.e., the destination. The result is taken modulo MOD
to ensure that it remains within the bounds specified by the problem statement.
This implementation effectively combines Dijkstra's algorithm for shortest paths with additional logic to concurrently count the paths without significantly deviating from the time complexity generally associated with Dijkstra's algorithm when used with an adjacency matrix.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example.
Consider a city with n = 4
intersections (0, 1, 2, 3) and the following roads
array:
roads = [ [0, 1, 4], // road from 0 to 1 with a travel time of 4 [0, 2, 3], // road from 0 to 2 with a travel time of 3 [1, 2, 1], // road from 1 to 2 with a travel time of 1 [1, 3, 2], // road from 1 to 3 with a travel time of 2 [2, 3, 2] // road from 2 to 3 with a travel time of 2 ]
Our task is to find the number of shortest paths from intersection 0 to intersection 3.
Following the solution approach:
- We create an adjacency matrix
g
of size 4x4, initialized withINF
, and populate it with the travel times from theroads
array:
| 0 1 2 3 --+------------ 0 | ∞ 4 3 ∞ 1 | 4 ∞ 1 2 2 | 3 1 ∞ 2 3 | ∞ 2 2 ∞
-
Initialize the
dist
array to[0, ∞, ∞, ∞]
andw
array to[1, 0, 0, 0]
. -
In the first iteration:
- Select intersection 0 (smallest
dist
and not visited). - Update distances and ways from intersection 0:
- For intersection 1:
dist[1] = 4
andw[1] = 1
. - For intersection 2:
dist[2] = 3
andw[2] = 1
.
- For intersection 1:
- Mark intersection 0 as visited.
- Select intersection 0 (smallest
-
In the second iteration:
- Select intersection 2 (smallest
dist
and not visited). - Update distances and ways from intersection 2:
- For intersection 1:
dist[1]
remains the same as the new distance is3 + 1 = 4
which is equal to the current distance, but we add the ways, sow[1] = w[1] + w[2] = 1 + 1 = 2
. - For intersection 3:
dist[3] = 3 + 2 = 5
andw[3] = 1
(there is now 1 shortest path to intersection 3 via 2).
- For intersection 1:
- Mark intersection 2 as visited.
- Select intersection 2 (smallest
-
In the third iteration:
- Select intersection 1 (smallest
dist
and not visited). - Update distances and ways from intersection 1:
- For intersection 3: New distance is
4 + 2 = 6
which is greater than currentdist[3]
, so we do nothing.
- For intersection 3: New distance is
- Mark intersection 1 as visited.
- Select intersection 1 (smallest
-
After visiting all intersections, we have the final array
dist
as[0, 4, 3, 5]
andw
as[1, 2, 1, 1]
. It means that the shortest distance to intersection 3 is 5 time units, and there arew[3] = 1
unique shortest paths to get there. -
The final result is
w[n - 1]
, which isw[3]
. Thus, there's 1 unique shortest way to travel from intersection 0 to intersection 3 in the minimum time possible. Since there's only 1 way, the answer (modulo10^9 + 7
) remains 1.
By following the steps outlined in the solution approach, we can see that the algorithm efficiently calculates both the shortest paths and their counts for this small example.
Solution Implementation
1from math import inf
2from typing import List
3
4class Solution:
5 def countPaths(self, n: int, roads: List[List[int]]) -> int:
6 # Constants for infinity and modulus
7 INF = inf
8 MOD = 10 ** 9 + 7
9
10 # Initialize the graph with infinite weights
11 graph = [[INF] * n for _ in range(n)]
12
13 # Populate graph with road travel times
14 for u, v, time in roads:
15 graph[u][v] = time
16 graph[v][u] = time
17
18 # Set the distance to the starting node 0 to 0
19 graph[0][0] = 0
20
21 # Initialize distance and ways arrays with infinite distance and zero ways
22 distance = [INF] * n
23 ways = [0] * n
24
25 # Start with the distance to node 0 to be 0 and the number of ways to 1
26 distance[0] = 0
27 ways[0] = 1
28
29 # Initialize visited array to track visited nodes
30 visited = [False] * n
31
32 # Perform Dijkstra's algorithm to find shortest paths
33 for _ in range(n):
34 # Find the unvisited node with the smallest distance
35 current_node = -1
36 for i in range(n):
37 if not visited[i] and (current_node == -1 or distance[i] < distance[current_node]):
38 current_node = i
39
40 # Mark this node as visited
41 visited[current_node] = True
42
43 # Update the distances and ways for neighboring nodes
44 for neighbor in range(n):
45 if neighbor == current_node:
46 continue
47 new_distance = distance[current_node] + graph[current_node][neighbor]
48
49 # If a shorter path is found, update the distance and ways
50 if distance[neighbor] > new_distance:
51 distance[neighbor] = new_distance
52 ways[neighbor] = ways[current_node]
53 # If another shortest path is found, increment the ways
54 elif distance[neighbor] == new_distance:
55 ways[neighbor] += ways[current_node]
56
57 # Return the number of shortest ways to the last node modulo MOD
58 return ways[n - 1] % MOD
59
1class Solution {
2 // Define constants for infinite distance and modulo value
3 private static final long INFINITY = Long.MAX_VALUE / 2;
4 private static final int MOD = (int) 1e9 + 7;
5
6 public int countPaths(int n, int[][] roads) {
7 long[][] graph = new long[n][n];
8 long[] distances = new long[n];
9 long[] ways = new long[n];
10 boolean[] visited = new boolean[n];
11
12 // Initialize the graph with infinite distances and distances array
13 for (int i = 0; i < n; ++i) {
14 Arrays.fill(graph[i], INFINITY);
15 Arrays.fill(distances, INFINITY);
16 }
17
18 // Fill the graph with actual road data
19 for (int[] road : roads) {
20 int from = road[0], to = road[1], time = road[2];
21 graph[from][to] = time;
22 graph[to][from] = time;
23 }
24
25 // Set the distance from start point to itself as zero
26 graph[0][0] = 0;
27 distances[0] = 0;
28 ways[0] = 1; // There's one way to reach the start point (itself)
29
30 // Dijkstra's Algorithm to find shortest paths
31 for (int i = 0; i < n; ++i) {
32 int current = -1;
33 // Find the unvisited vertex with the smallest distance
34 for (int j = 0; j < n; ++j) {
35 if (!visited[j] && (current == -1 || distances[j] < distances[current])) {
36 current = j;
37 }
38 }
39 visited[current] = true;
40
41 // Update distances and count of ways for all neighbors
42 for (int j = 0; j < n; ++j) {
43 if (j == current) {
44 continue; // Skip if it's the current vertex
45 }
46
47 long newDistance = distances[current] + graph[current][j];
48
49 // If a shorter path to neighbor is found, update the distance and ways
50 if (distances[j] > newDistance) {
51 distances[j] = newDistance;
52 ways[j] = ways[current];
53 }
54 // If another path with the same length is found, increment the ways
55 else if (distances[j] == newDistance) {
56 ways[j] = (ways[j] + ways[current]) % MOD;
57 }
58 }
59 }
60
61 // Return the number of ways to reach the last vertex (n-1)
62 return (int) ways[n - 1];
63 }
64}
65
1#include <vector>
2#include <queue>
3#include <climits>
4
5using namespace std;
6
7typedef long long ll;
8
9class Solution {
10public:
11 // Constants for the problem limits.
12 const ll INF = LLONG_MAX / 2; // Define infinity as half the maximum value to avoid overflow.
13 const int MOD = 1e9 + 7; // Modulo value for the number of paths.
14
15 int countPaths(int n, vector<vector<int>>& roads) {
16 // Graph represented as adjacency list, where g[u] holds pairs (v, t) for edge u-v with travel time t.
17 vector<vector<pair<int, ll>>> graph(n);
18 // Initialize distances array with infinite distances and set start node distance to 0.
19 vector<ll> distances(n, INF);
20 // Ways array to hold the number of ways to reach each node.
21 vector<ll> ways(n, 0);
22 // Visited array to keep track of visited nodes.
23 vector<bool> visited(n, false);
24
25 // Build the graph from road information.
26 for (auto& road : roads) {
27 int u = road[0], v = road[1];
28 ll t = road[2];
29 graph[u].emplace_back(v, t);
30 graph[v].emplace_back(u, t);
31 }
32
33 // Using priority queue to hold pairs of (distance, node), for getting the next closest unvisited node.
34 priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
35
36 // Initialize starting values for node 0.
37 distances[0] = 0;
38 ways[0] = 1;
39 pq.push({0, 0});
40
41 // Dijkstra's algorithm for shortest paths.
42 while (!pq.empty()) {
43 auto [distance, u] = pq.top();
44 pq.pop();
45 if (visited[u])
46 continue;
47 visited[u] = true;
48
49 // Iterate over all neighbors of the current node.
50 for (auto& [v, t] : graph[u]) {
51 ll nextDistance = distances[u] + t;
52 // If a shorter path is found, update distance and ways.
53 if (distances[v] > nextDistance) {
54 distances[v] = nextDistance;
55 ways[v] = ways[u];
56 pq.push({nextDistance, v});
57 // If an equal distance path is found, add ways.
58 } else if (distances[v] == nextDistance) {
59 ways[v] = (ways[v] + ways[u]) % MOD;
60 }
61 }
62 }
63
64 // Return the number of ways to reach the last node.
65 return ways[n - 1];
66 }
67};
68
1type Pair<T, U> = [T, U];
2
3// Define infinity as half the maximum safe integer value in JavaScript to avoid overflow.
4const INF: number = Number.MAX_SAFE_INTEGER / 2;
5// Modulo value for the number of paths.
6const MOD: number = 1e9 + 7;
7
8// Graph represented as adjacency list, where graph[u] holds tuples (v, t) for edge u-v with travel time t.
9let graph: Pair<number, number>[][] = [];
10
11// Initialize distances array with infinite distances and then set the start node distance to 0.
12let distances: number[] = [];
13// Ways array to hold the number of ways to reach each node.
14let ways: number[] = [];
15// Visited set to keep track of visited nodes.
16let visited: boolean[] = [];
17
18// Dijkstra's algorithm for shortest paths.
19function dijkstra(n: number): void {
20 // Priority queue to hold tuples of (distance, node), for getting the next closest unvisited node.
21 const pq: Pair<number, number>[] = [];
22
23 // Convenience method to handle the priority queue.
24 const enqueue = (distance: number, node: number) => {