Suppose you are given an undirected weighted graph G(V,E) and 2 vertices v, u. There are N vertices and E edges.
There can be multiple paths between those 2 vertices. For each path, select the maximum weight lying on that path. Out of all these maximum elements, find the minimum.
Initially, I was trying to solve this using DP but I couldn't find a way. Then, I thought of building a MST using Prim's Algorithm as we can get that minimum of maximums if we eliminate all the bigger elements. Eventually, I simply used Dijkstra's Algorithm where I replaced the sum function with min function. Basically, I was creating a tree rooted at v and selected N-1 minimum weight edges to make a tree.
This requires a priority queue and works in O(E log(E)). Can I optimised it to run faster. Something close to constant time (O(V + E))?
I was gonna say prim adding for dense graph you can use N^2 version and for sparse graph priority queue version E log (V)
Check this out: https://blogs.asarkar.com/algorithms-design-analysis/hw-5-opt/
I Googles ‘minimum bottleneck path linear’ (this is how your problem is called.
As a personal note, I would not choose the median edge as the article suggests, but rather some random pivot (like in QuickSelect algorithm). Not sure if it will make it much faster, though.