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 value 10^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.

Example 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:

1roads = [
2    [0, 1, 4],   // road from 0 to 1 with a travel time of 4
3    [0, 2, 3],   // road from 0 to 2 with a travel time of 3
4    [1, 2, 1],   // road from 1 to 2 with a travel time of 1
5    [1, 3, 2],   // road from 1 to 3 with a travel time of 2
6    [2, 3, 2]    // road from 2 to 3 with a travel time of 2
7]

Our task is to find the number of shortest paths from intersection 0 to intersection 3.

Following the solution approach:

1. We create an adjacency matrix g of size 4x4, initialized with INF, and populate it with the travel times from the roads array:

1  | 0  1  2  3
2--+------------
30 | ∞  4  3  ∞
41 | 4  ∞  1  2
52 | 3  1  ∞  2
63 | ∞  2  2  ∞

2. Initialize the dist array to [0, ∞, ∞, ∞] and w array to [1, 0, 0, 0].

3. 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 and w[1] = 1.
     • For intersection 2: dist[2] = 3 and w[2] = 1.
   • Mark intersection 0 as visited.

4. 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 is 3 + 1 = 4 which is equal to the current distance, but we add the ways, so w[1] = w[1] + w[2] = 1 + 1 = 2.
     • For intersection 3: dist[3] = 3 + 2 = 5 and w[3] = 1 (there is now 1 shortest path to intersection 3 via 2).
   • Mark intersection 2 as visited.

5. 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 current dist[3], so we do nothing.
   • Mark intersection 1 as visited.

6. After visiting all intersections, we have the final array dist as [0, 4, 3, 5] and w as [1, 2, 1, 1]. It means that the shortest distance to intersection 3 is 5 time units, and there are w[3] = 1 unique shortest paths to get there.

7. The final result is w[n - 1], which is w[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 (modulo 10^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

Time and Space Complexity

The provided Python code is an implementation of Dijkstra's algorithm to find the shortest paths from a single source to all other nodes in a graph, here specifically tailored to count all the distinct ways one can travel from node 0 to node n-1 given the list of roads. Each road has two nodes it connects and the time taken to travel that road.

Time Complexity

The time complexity of the code depends on two nested loops: the outer loop runs n times (where n is the number of nodes), and the inner loop, which in the worst case, also runs n times to find the node with the minimum distance that hasn't been visited yet.

Furthermore, the adjacent nodes are visited in another nested loop that also iterates up to n times. Consequently, the worst-case time complexity of this algorithm is O(n^3), since for each node, we potentially inspect all other nodes to update the distances and ways.

Space Complexity

The space complexity is primarily dependent on the storage of the graph, distance array, ways array, and the visited array.

• Graph g is represented as a 2D matrix and occupies O(n^2) space.
• Distance array dist, ways array w, and visited array vis each take O(n) space.

Adding these up gives us a total space complexity of O(n^2), with the graph matrix being the dominant term.

Learn more about how to find time and space complexity quickly using problem constraints.