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?
All-pairs minimax path problem - MST
algorithms;weighted graphs;minimum spanning tree