Number of Ways to Arrive at Destination
Problem Description
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.
Solve it on LeetCode
Approaches
1. Dijkstra's Algorithm with DFS
Intuition:
In this approach, we'll use the famous Dijkstra's Algorithm to find the shortest path from the source to the destination. After finding the shortest path, we can perform a DFS from the destination to the source to count all the possible paths matching this shortest path length. This approach is still efficient for the input size allowed by the problem constraints.
Algorithm:
- Utilize Dijkstra's Algorithm to ensure all minimum weights from the source to all other nodes.
- Once the shortest path weights are captured, use DFS from the destination to the source counting all possible paths that equal this shortest path weight.
- Ensure to mod the result by (10^9 + 7).
Code:
- Time Complexity: O(E log V), where E is the number of roads and V is the number of cities.
- Space Complexity: O(V + E) due to the adjacency list and other data structures used.
2. Dijkstra's Algorithm with Dynamic Programming
Intuition:
In this approach, instead of using DFS to count paths after Dijkstra's, we integrate the counting mechanism into Dijkstra’s Algorithm itself. This involves maintaining a separate array to count the number of ways to reach each node, updating it as we discover the shortest paths.
Algorithm:
- Use Dijkstra's Algorithm to compute both the shortest distances and count ways dynamically.
- Maintain an array to track the number of ways to reach a node when processing its neighbors in the priority queue.
- If a shorter path found to a node, update the path count to that node as that of the current node.
- If another equal shortest path found, add the current node's path count to that node's path count.
Code:
- Time Complexity: O(E log V), where E is the number of roads and V is the number of cities. The performance is similar to standard Dijkstra due to the priority queue.
- Space Complexity: O(V + E), stemming from the adjacency list representation and extra counting array.