Path with Minimum Maximum Weight — Binary Search + BFS

Problem

Find a path from node 0 to node n-1 that minimises the maximum edge weight along the path.

Approach: Binary search on the max-edge value. For each candidate mid, check if path exists using only edges with weight ≤ mid.

Solution

Python

from collections import defaultdict, deque

def minMaxPath(n, edges, src, dst):
    adj = defaultdict(list)
    weights = set()
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
        weights.add(w)
    weights = sorted(weights)

    def reachable(limit):
        q = deque([src])
        vis = {src}
        while q:
            u = q.popleft()
            if u == dst: return True
            for v, w in adj[u]:
                if w <= limit and v not in vis:
                    vis.add(v)
                    q.append(v)
        return False

    lo, hi = 0, len(weights)-1
    ans = weights[-1]
    while lo <= hi:
        mid = (lo+hi)//2
        if reachable(weights[mid]):
            ans = weights[mid]
            hi = mid-1
        else:
            lo = mid+1
    return ans

JavaScript

function minMaxPath(n,edges,src,dst){
    const adj=Array.from({length:n},()=>[]),ws=new Set();
    for(const[u,v,w]of edges){adj[u].push([v,w]);adj[v].push([u,w]);ws.add(w);}
    const wArr=[...ws].sort((a,b)=>a-b);
    const ok=(lim)=>{const vis=new Set([src]),q=[src];while(q.length){const u=q.shift();if(u===dst)return true;for(const[v,w]of adj[u])if(w<=lim&&!vis.has(v)){vis.add(v);q.push(v);}}return false;};
    let lo=0,hi=wArr.length-1,ans=wArr[hi];
    while(lo<=hi){const mid=(lo+hi)>>1;if(ok(wArr[mid])){ans=wArr[mid];hi=mid-1;}else lo=mid+1;}
    return ans;
}

Java / C++ / C

/* Same pattern: collect unique weights, sort, binary search + BFS check */