{x}
blog image

Number of Ways to Arrive at Destination

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:

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.

Solution Explanation: Counting Paths in a Graph with Dijkstra's Algorithm

This problem asks to find the number of ways to reach the destination node (n-1) from the source node (0) in the shortest possible time within a graph represented by the roads array. The solution uses a modified Dijkstra's algorithm to achieve this.

Algorithm:

  1. Graph Representation: The input roads array is used to construct an adjacency matrix g. g[i][j] represents the travel time between nodes i and j. If there's no direct road, it's initialized to infinity.

  2. Initialization:

    • dist[i] stores the shortest time to reach node i from the source. Initially, dist[0] = 0 and all others are infinity.
    • f[i] stores the number of shortest paths to reach node i from the source. f[0] = 1.
    • vis[i] keeps track of whether node i has been visited.

  3. Modified Dijkstra's Algorithm: The algorithm iterates through the nodes, selecting the unvisited node with the minimum dist value at each step.

  4. Path Counting: For each neighbor j of the selected node t, the algorithm checks:

    • If dist[j] is greater than the current shortest distance to j (dist[t] + g[t][j]): This means a shorter path is found. Update dist[j] and set f[j] to the number of shortest paths to t (f[t]).
    • If dist[j] is equal to the current shortest distance to j: This means another path with the same shortest distance is found. Increment f[j] by the number of shortest paths to t.

  5. Modulo Operation: The f[i] values are updated using the modulo operator (% (10^9 + 7)) to prevent integer overflow.

  6. Result: Finally, f[n-1] contains the number of shortest paths to the destination node (n-1).

Time and Space Complexity:

  • Time Complexity: The dominant factor is the Dijkstra's algorithm, which has a time complexity of O(n^2) using a naive implementation with adjacency matrix. More sophisticated implementations using priority queues can reduce this to O(E log V), where E is the number of edges and V is the number of vertices (nodes). In this problem, E can be at most O(n^2).

  • Space Complexity: The space complexity is O(n^2) because of the adjacency matrix g. Other arrays (dist, f, vis) take O(n) space.

Code Examples (Python, Java, C++, Go, TypeScript):

The provided code examples in the different programming languages implement the algorithm described above. They all follow the same logic, differing only in syntax and language-specific features. The key elements—g, dist, f, vis, and the Dijkstra's algorithm logic—are consistently implemented across all the languages.