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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

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  341 | 41  2
52 | 3  12
63 | ∞  2  2
  1. Initialize the dist array to [0, ∞, ∞, ∞] and w array to [1, 0, 0, 0].

  2. 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.
  3. 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.
  4. 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.
  5. 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.

  6. 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

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) => {
25        pq.push([distance, node]);
26        // Sort to ensure we are popping the node with the smallest distance next.
27        pq.sort((a, b) => a[0] - b[0]);
28    };
29
30    const dequeue = (): Pair<number, number> => {
31        return pq.shift()!;
32    };
33
34    // Initialize starting values for node 0.
35    distances[0] = 0;
36    ways[0] = 1;
37    enqueue(0, 0);
38
39    while (pq.length > 0) {
40        const [distance, u] = dequeue();
41
42        if (visited[u]) continue;
43        visited[u] = true;
44
45        graph[u].forEach(([v, t]) => {
46            const nextDistance: number = distances[u] + t;
47            // If a shorter path is found, update distance and ways.
48            if (distances[v] > nextDistance) {
49                distances[v] = nextDistance;
50                ways[v] = ways[u];
51                enqueue(nextDistance, v);
52            // If an equal distance path is found, add ways.
53            } else if (distances[v] === nextDistance) {
54                ways[v] = (ways[v] + ways[u]) % MOD;
55            }
56        });
57    }
58}
59
60// Method to count the number of paths from node 0 to node n-1.
61function countPaths(n: number, roads: number[][]): number {
62    graph = Array.from({ length: n }, () => []);
63    distances = new Array(n).fill(INF);
64    ways = new Array(n).fill(0);
65    visited = new Array(n).fill(false);
66
67    // Build the graph from road information.
68    roads.forEach(([u, v, t]) => {
69        graph[u].push([v, t]);
70        graph[v].push([u, t]);
71    });
72
73    // Run Dijkstra's algorithm.
74    dijkstra(n);
75
76    // Return the number of ways to reach the last node.
77    return ways[n - 1];
78}
79

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄