Minimize the Maximum Edge on a Path
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Minimize the Maximum Edge on a Path
You are given a weighted undirected graph and two vertices, `start` and `target`. Define the stress of a path as the largest edge weight used by that path. Return the minimum possible stress among all paths from `start` to `target`. Return `-1` when no such path exists.
### Function Signature
```python
def minimum_path_stress(
n: int,
edges: list[tuple[int, int, int]],
start: int,
target: int,
) -> int:
...
```
### Input
- Vertices are numbered from `0` through `n - 1`.
- Each edge is `(u, v, weight)` and may be traversed in either direction.
- Parallel edges are allowed.
### Output
Return the smallest achievable maximum edge weight, or `-1` if `target` is unreachable. If `start == target`, return `0`.
### Constraints
- `1 <= n <= 200_000`
- `0 <= len(edges) <= 300_000`
- `1 <= weight <= 10**9`
- `0 <= start, target < n`
### Example
```text
n = 5
edges = [(0, 1, 8), (0, 2, 3), (2, 1, 4), (1, 3, 6), (2, 3, 10)]
start = 0
target = 3
Output: 6
```
The path `0 -> 2 -> 1 -> 3` has edge weights `3, 4, 6`, so its stress is `6`. No path reaches vertex `3` using only edges lighter than `6`.
### Clarifications
- Minimize the largest edge, not the sum of edge weights.
- The graph is not guaranteed to be connected.
Quick Answer: Find a path in a weighted undirected graph that minimizes its largest edge rather than the sum of weights. Handle parallel edges, disconnected vertices, and the start-equals-target case efficiently at large graph scale.
In a weighted undirected graph, return the smallest possible maximum edge weight on a path from start to target. Return -1 when target is unreachable and 0 when start equals target.
Constraints
- Vertices are numbered 0 through n-1.
- Edge weights are positive integers.
- Parallel edges are allowed.
- The graph may be disconnected.
- Minimize the largest edge, not the sum.
Examples
Input: (1, [], 0, 0)
Expected Output: 0
Explanation: A vertex reaches itself without using an edge.
Input: (3, [], 0, 2)
Expected Output: -1
Explanation: Disconnected vertices are unreachable.
Hints
- Adapt Dijkstra's algorithm so path cost is the maximum edge seen so far.
- Relax an edge with max(current_stress, edge_weight).
- The first finalized target value is optimal.