Find Shortest Paths to Target Nodes
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a weighted directed graph representing distances between nodes.
- There are `n` nodes labeled from `0` to `n - 1`.
- `edges[i] = [u, v, w]` means there is a directed edge from node `u` to node `v` with positive distance `w`.
- You are given a starting node `source`.
- You are also given a list of target nodes `targets`.
Return the shortest distance from `source` to each target node. If a target cannot be reached from `source`, return `-1` for that target.
The result should preserve the order of `targets`.
Example:
```text
n = 5
edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]]
source = 0
targets = [1, 3, 4]
```
Output:
```text
[3, 4, 7]
```
Explanation:
- The shortest path from `0` to `1` is `0 -> 2 -> 1`, with distance `1 + 2 = 3`.
- The shortest path from `0` to `3` is `0 -> 2 -> 1 -> 3`, with distance `1 + 2 + 1 = 4`.
- The shortest path from `0` to `4` is `0 -> 2 -> 1 -> 3 -> 4`, with distance `1 + 2 + 1 + 3 = 7`.
Constraints:
- `1 <= n <= 10^5`
- `0 <= edges.length <= 2 * 10^5`
- `edges[i].length == 3`
- `0 <= u, v < n`
- `1 <= w <= 10^9`
- `0 <= source < n`
- `1 <= targets.length <= n`
- All edge weights are positive.
Quick Answer: This question evaluates knowledge of graph algorithms and algorithmic problem-solving, specifically computing shortest paths in weighted directed graphs and handling unreachable targets.
You are given a weighted directed graph with `n` nodes labeled from `0` to `n - 1`. Each entry `edges[i] = [u, v, w]` represents a directed edge from node `u` to node `v` with positive weight `w`.
Given a starting node `source` and a list of `targets`, return a list where each element is the shortest distance from `source` to the corresponding target node. If a target cannot be reached from `source`, return `-1` for that target.
The order of the returned distances must match the order of `targets` exactly.
Constraints
- 1 <= n <= 10^5
- 0 <= len(edges) <= 2 * 10^5
- edges[i].length == 3
- 0 <= u, v < n
- 1 <= w <= 10^9
- 0 <= source < n
- 1 <= len(targets) <= n
- All edge weights are positive.
Examples
Input: (5, [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]], 0, [1, 3, 4])
Expected Output: [3, 4, 7]
Explanation: The best routes are 0->2->1 with cost 3, 0->2->1->3 with cost 4, and 0->2->1->3->4 with cost 7.
Input: (4, [[0, 1, 2], [1, 2, 3]], 0, [2, 3, 0])
Expected Output: [5, -1, 0]
Explanation: Node 2 is reachable with cost 5, node 3 is unreachable, and the distance from the source to itself is 0.
Hints
- Because all edge weights are positive, a shortest-path algorithm based on a min-heap is a good fit.
- You only need one run from `source`: compute distances to all reachable nodes, then read off the answers for each target in order.