muzare_ali's blog

Find the minimum of maximum weight on all possible paths between 2 vertices v and u.
By muzare_ali, history, 3 years ago, In English

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))?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check this out: https://blogs.asarkar.com/algorithms-design-analysis/hw-5-opt/

How did I find this gem?

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.

→ Reply