# Number of Ways to Arrive at Destination **Difficulty:** MEDIUM [External](https://leetcode.com/problems/number-of-ways-to-arrive-at-destination) Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-arrive-at-destination **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path) **Data structures:** Graph --- ## Problem You are in a city that consists of `n` intersections numbered from `0` to `n - 1` with **bi-directional** roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections. You are given an integer `n` and a 2D integer array `roads` where `roads[i] = [ui, vi, timei]` means that there is a road between intersections `ui` and `vi` that takes `timei` minutes to travel. You want to know in how many ways you can travel from intersection `0` to intersection `n - 1` in the **shortest amount of time**. Return _the **number of ways** you can arrive at your destination in the **shortest amount of time**_. Since the answer may be large, return it **modulo** `109 + 7`. **Example 1:** ![](https://assets.glich.co/dsa/number-of-ways-to-arrive-at-destination/image0.png) **Input:** 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]] **Output:** 4 **Explanation:** The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes. The four ways to get there in 7 minutes are: - 0 ➝ 6 - 0 ➝ 4 ➝ 6 - 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6 - 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6 **Example 2:** **Input:** n = 2, roads = [[1,0,10]] **Output:** 1 **Explanation:** There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes. **Constraints:** * `1 <= n <= 200` * `n - 1 <= roads.length <= n * (n - 1) / 2` * `roads[i].length == 3` * `0 <= ui, vi <= n - 1` * `1 <= timei <= 109` * `ui != vi` * There is at most one road connecting any two intersections. * You can reach any intersection from any other intersection. # Approaches ## Modified Floyd-Warshall Algorithm This approach uses a dynamic programming technique, the Floyd-Warshall algorithm, to find the shortest paths between all pairs of intersections. We modify the standard algorithm to not only track the shortest distance but also the number of ways to achieve that shortest distance. **Time:** O(n^3) due to the three nested loops. This is feasible for the given constraint of n <= 200. · **Space:** O(n^2) to store the `dist` and `ways` matrices. **Pros:** Relatively straightforward to implement using nested loops.; The logic is self-contained and doesn't require complex data structures like priority queues. **Cons:** Less efficient than Dijkstra's algorithm, especially for sparse graphs.; Calculates shortest paths between all pairs of nodes, which is more work than required for this problem (we only need 0 to n-1). ### Explanation The core idea is to iteratively consider each intersection `k` as an intermediate point in paths between any two intersections `i` and `j`. We maintain two 2D arrays: `dist[i][j]` for the shortest time from `i` to `j`, and `ways[i][j]` for the count of such paths. We initialize these matrices based on direct roads. Then, for every possible intermediate node `k`, we check if going from `i` to `j` through `k` improves the path. If `dist[i][k] + dist[k][j]` gives a shorter path to `j`, we update `dist[i][j]` and set the number of ways to `ways[i][k] * ways[k][j]`. If it results in a path of the same length, we add `ways[i][k] * ways[k][j]` to the existing `ways[i][j]`. After checking all intermediate nodes, `ways[0][n-1]` will hold the required count. ```java class Solution { public int countPaths(int n, int[][] roads) { long MOD = 1_000_000_007; long[][] dist = new long[n][n]; long[][] ways = new long[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) { dist[i][j] = Long.MAX_VALUE / 2; // Use a large value to avoid overflow } } ways[i][i] = 1; } for (int[] road : roads) { int u = road[0]; int v = road[1]; int time = road[2]; dist[u][v] = time; dist[v][u] = time; ways[u][v] = 1; ways[v][u] = 1; } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; ways[i][j] = (ways[i][k] * ways[k][j]) % MOD; } else if (dist[i][k] + dist[k][j] == dist[i][j]) { ways[i][j] = (ways[i][j] + (ways[i][k] * ways[k][j]) % MOD) % MOD; } } } } return (int) ways[0][n - 1]; } } ``` ### Algorithm - Create two 2D arrays: `dist[n][n]` to store the shortest time from intersection `i` to `j`, and `ways[n][n]` to store the number of shortest paths from `i` to `j`. - Initialize `dist` with a very large value for all pairs, `0` for `dist[i][i]`, and the given road times for direct connections. - Initialize `ways` with `0` for all pairs, `1` for `ways[i][i]`, and `1` for direct connections. - Iterate through all possible intermediate intersections `k` from `0` to `n-1`. - For each pair of intersections `(i, j)`, check if the path from `i` to `j` via `k` (`dist[i][k] + dist[k][j]`) is better. - If `dist[i][k] + dist[k][j] < dist[i][j]`: A new, shorter path is found. Update `dist[i][j]` and set `ways[i][j] = (ways[i][k] * ways[k][j]) % MOD`. - If `dist[i][k] + dist[k][j] == dist[i][j]`: An alternative path of the same shortest length is found. Update `ways[i][j] = (ways[i][j] + ways[i][k] * ways[k][j]) % MOD`. - After all iterations, `ways[0][n-1]` contains the final answer. ## Modified Dijkstra's Algorithm This is the most efficient approach for this problem. It uses Dijkstra's algorithm, which is designed to find the shortest paths from a single source in a graph with non-negative edge weights. We augment the standard algorithm to also count the number of shortest paths as it explores the graph. **Time:** O(E log n), where `n` is the number of intersections and `E` is the number of roads. The `log n` factor comes from the priority queue operations. · **Space:** O(n + E), where `n` is the number of intersections and `E` is the number of roads. This is for the adjacency list, `dist` and `ways` arrays, and the priority queue. **Pros:** Most efficient algorithm for this problem, especially on sparse graphs.; It is the standard algorithm for single-source shortest path problems with non-negative weights. **Cons:** Slightly more complex to implement than Floyd-Warshall due to the use of a priority queue and adjacency list. ### Explanation We start from the source node `0` and explore the graph greedily. We use two arrays: `dist[i]` to keep track of the shortest time found so far to reach node `i`, and `ways[i]` to count the number of paths that achieve this shortest time. A priority queue is used to always process the node that is closest to the source. Initially, `dist[0]` is 0 with `ways[0]` being 1. All other distances are infinity. We pull the node `u` with the smallest distance from the priority queue. For each of its neighbors `v`, we check if reaching it via `u` provides a better or equally good path. - If `dist[u] + time_uv < dist[v]`, we've found a completely new shortest path to `v`. We update `dist[v]` and set `ways[v]` to be the same as `ways[u]`, as any shortest path to `v` must now come through one of the shortest paths to `u`. - If `dist[u] + time_uv == dist[v]`, we've found an alternative way to reach `v` in the same shortest time. We add the number of ways to reach `u` (`ways[u]`) to `ways[v]`. This process continues until all reachable nodes are visited. The final answer is `ways[n-1]`. ```java class Solution { public int countPaths(int n, int[][] roads) { long MOD = 1_000_000_007; List> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] road : roads) { adj.get(road[0]).add(new int[]{road[1], road[2]}); adj.get(road[1]).add(new int[]{road[0], road[2]}); } long[] dist = new long[n]; long[] ways = new long[n]; Arrays.fill(dist, Long.MAX_VALUE); dist[0] = 0; ways[0] = 1; // PriorityQueue stores {time, node} PriorityQueue pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0])); pq.offer(new long[]{0, 0}); while (!pq.isEmpty()) { long[] current = pq.poll(); long time = current[0]; int u = (int) current[1]; // If we found a shorter path already, skip if (time > dist[u]) { continue; } for (int[] neighbor : adj.get(u)) { int v = neighbor[0]; int time_uv = neighbor[1]; // Found a new shorter path if (dist[u] + time_uv < dist[v]) { dist[v] = dist[u] + time_uv; ways[v] = ways[u]; pq.offer(new long[]{dist[v], v}); } // Found another path with the same shortest time else if (dist[u] + time_uv == dist[v]) { ways[v] = (ways[v] + ways[u]) % MOD; } } } return (int) ways[n - 1]; } } ``` ### Algorithm - Create an adjacency list representation of the graph. - Initialize a `dist` array of size `n` with infinity and a `ways` array of size `n` with 0. - Set `dist[0] = 0` and `ways[0] = 1`. - Create a priority queue `pq` that sorts entries `(time, node)` by `time`. Add `(0, 0)` to `pq`. - While `pq` is not empty: - Extract the node `u` with the minimum time `t` from `pq`. - If `t > dist[u]`, it's an outdated entry, so skip it. - For each neighbor `v` of `u`: - If `dist[u] + time_to_v < dist[v]`: A new shorter path is found. Update `dist[v]`, set `ways[v] = ways[u]`, and add `(dist[v], v)` to `pq`. - Else if `dist[u] + time_to_v == dist[v]`: Another path of the same shortest length is found. Update `ways[v]` by adding `ways[u]` to it (modulo `10^9 + 7`). - Return `ways[n-1]` as the final answer. # Solutions ### Java ```java class Solution { private static final long INF = Long.MAX_VALUE / 2; private static final int MOD = (int)1 e9 + 7; public int countPaths(int n, int[][] roads) { long[][] g = new long[n][n]; long[] dist = new long[n]; long[] w = new long[n]; boolean[] vis = new boolean[n]; for (int i = 0; i < n; ++i) { Arrays.fill(g[i], INF); Arrays.fill(dist, INF); } for (int[] r : roads) { int u = r[0], v = r[1], t = r[2]; g[u][v] = t; g[v][u] = t; } g[0][0] = 0; dist[0] = 0; w[0] = 1; for (int i = 0; i < n; ++i) { int t = -1; for (int j = 0; j < n; ++j) { if (!vis[j] && (t == -1 || dist[j] < dist[t])) { t = j; } } vis[t] = true; for (int j = 0; j < n; ++j) { if (j == t) { continue; } long ne = dist[t] + g[t][j]; if (dist[j] > ne) { dist[j] = ne; w[j] = w[t]; } else if (dist[j] == ne) { w[j] = (w[j] + w[t]) % MOD; } } } return (int)w[n - 1]; } } ``` ### CPP ```cpp typedef long long ll ; class Solution { public: const ll INF = LLONG_MAX / 2 ; const int MOD = 1e9 + 7 ; int countPaths ( int n , vector < vector < int >>& roads ) { vector < vector < ll >> g ( n , vector < ll > ( n , INF )); vector < ll > dist ( n , INF ); vector < ll > w ( n ); vector < bool > vis ( n ); for ( auto & r : roads ) { int u = r [ 0 ], v = r [ 1 ], t = r [ 2 ]; g [ u ][ v ] = t ; g [ v ][ u ] = t ; } g [ 0 ][ 0 ] = 0 ; dist [ 0 ] = 0 ; w [ 0 ] = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int t = - 1 ; for ( int j = 0 ; j < n ; ++ j ) { if ( ! vis [ j ] && ( t == - 1 || dist [ t ] > dist [ j ])) t = j ; } vis [ t ] = true ; for ( int j = 0 ; j < n ; ++ j ) { if ( t == j ) continue ; ll ne = dist [ t ] + g [ t ][ j ]; if ( dist [ j ] > ne ) { dist [ j ] = ne ; w [ j ] = w [ t ]; } else if ( dist [ j ] == ne ) w [ j ] = ( w [ j ] + w [ t ]) % MOD ; } } return w [ n - 1 ]; } }; ``` ### Python ```python ''' In Python 3, 10**9 + 7 is a commonly used constant in competitive programming and algorithmic contests. It is often used as a modular arithmetic prime number for computing hash values, counting permutations and combinations, and in various other mathematical computations. The reason for using 10**9 + 7 is that it is a large prime number that fits within the 32-bit integer limit. This means that arithmetic operations on this number can be performed efficiently using 32-bit integer arithmetic, which is significantly faster than using 64-bit arithmetic. Furthermore, 10**9 + 7 is a safe prime, which means that it has certain properties that make it useful for cryptographic applications. Specifically, it is a prime of the form 2*p + 1, where p is also a prime. This means that it has a large prime factor, making it difficult to factorize and making it suitable for use in cryptographic algorithms. Overall, the number 10**9 + 7 is a useful constant in Python 3 and is often used in algorithmic programming for its properties as a large prime and a safe prime. ''' class Solution : def countPaths ( self , n : int , roads : List [ List [ int ]]) -> int : G = defaultdict ( list ) for x , y , w in roads : G [ x ]. append (( y , w )) G [ y ]. append (( x , w )) time_cost = [ float ( 'inf' )] * n time_cost [ 0 ] = 0 path_cnt = [ 0 ] * n path_cnt [ 0 ] = 1 heap = [( 0 , 0 )] # (min_cost, idx) , default order min->max while heap : ( min_cost , idx ) = heappop ( heap ) if idx == n - 1 : return path_cnt [ idx ] % ( 10 ** 9 + 7 ) # or just break out of this while loop for neib , weight in G [ idx ]: candidate = min_cost + weight if candidate == time_cost [ neib ]: # add new paths to counting paths reaching 'neib' path_cnt [ neib ] += path_cnt [ idx ] # '+=' # no heap pushing elif candidate < time_cost [ neib ]: # dist[neib] initialized as float('inf') time_cost [ neib ] = candidate path_cnt [ neib ] = path_cnt [ idx ] # '=' heappush ( heap , ( candidate , neib )) return path_cnt [ - 1 ] # i.e. 0 ############ class Solution : def countPaths ( self , n : int , roads : List [ List [ int ]]) -> int : INF = inf MOD = 10 ** 9 + 7 g = [[ INF ] * n for _ in range ( n )] for u , v , t in roads : g [ u ][ v ] = t g [ v ][ u ] = t g [ 0 ][ 0 ] = 0 dist = [ INF ] * n w = [ 0 ] * n dist [ 0 ] = 0 w [ 0 ] = 1 vis = [ False ] * n for _ in range ( n ): t = - 1 for i in range ( n ): if not vis [ i ] and ( t == - 1 or dist [ i ] < dist [ t ]): t = i vis [ t ] = True for i in range ( n ): if i == t : continue ne = dist [ t ] + g [ t ][ i ] if dist [ i ] > ne : dist [ i ] = ne w [ i ] = w [ t ] elif dist [ i ] == ne : w [ i ] += w [ t ] return w [ - 1 ] % MOD ```