# All-pairs minimax path problem - MST [closed]

Let $G(V, E)$ be an undirected weighted (positive) graph. Given a path $s-t$ find the path that minimizes the maximum weight of any of its edges. This is the minimax path problem.

It is know that a minimum spanning tree $T$ of $G$ gives a minimax path between every pair of nodes. After calculating the MST I want to be able to query any pair of nodes and get the "heaviest" edge of the path in the tree. Ideally I would like to preprocess the MST in linear time and query in constant time.

Wikipedia provide a $O(1)$ lookup with Cartesian trees (preprocess in linear time) and lowest common ancestor but I don't understand it.

Any ideas?

• You mention that Wikipedia already has a solution – perhaps you should try to understand it? – Yuval Filmus Jan 10 '17 at 19:34
• Indeed. But I don't quite get it and tried a lot. Also I would like to know if there are other approaches. Thanks! – Laxmana Jan 10 '17 at 19:36
• What specifically don't you understand in Wikipedia's solution? – Raphael Jan 10 '17 at 21:50
• I don't understand how you construct the tree. I understand that you start with the heaviest edge and put it to the root but I am confused what you do next. Also how leaves of the Cartesian tree represent the vertices of the Graph? The previous nodes are the weights of the edges right? – Laxmana Jan 11 '17 at 10:40
• Also, although I understand why you put it on hold I believe that my question is clear. I am not asking an explanation on the wikipedia article. I am asking for approaches and ideas for the problem. Ie it could be done with BFS/DFS. I provided Wikipedia as a reference. – Laxmana Jan 11 '17 at 10:43