A Faster Algorithm for Least Deviant Path

The least deviant path was defined by Klostermeyer \([1]\) as the path between two vertices \(u\) and \(v\) that minimizes the difference between the largest and smallest weights on the path. This paper presents an \(O(E \log E)\) time algorithm for this problem in undirected graphs, improving upon the previously given \(O(E^{1.793})\) time algorithm.
The same algorithm can also be used to solve the problem in \(O(VE)\) time in directed graphs.