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

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

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.

Minimize the Maximum Edge on a Path

Hints

1. Adapt Dijkstra's algorithm so path cost is the maximum edge seen so far.
2. Relax an edge with max(current_stress, edge_weight).
3. The first finalized target value is optimal.

Approach

This is Dijkstra's algorithm over the bottleneck path metric. Extending a path changes its stress to the maximum of its prior stress and the new edge. That metric is monotone, so the minimum heap finalizes vertices safely.

• Time complexity: O((n + e) log n).
• Space complexity: O(n + e).