Fast and fine quickest path algorithm

•A novel quickest path algorithm is proposed.•The algorithm runs in O(r(m+nlogn))O(r(m+nlogn)) time and uses O(m+n)O(m+n) space.•It is a ratio-labeling algorithm working as a Dijkstra-like method.•The method enumerates only supported efficient paths.•Computational tests show that the algorithm performs very well.

We address the quickest path problem proposing a new algorithm based on the fact that its optimal solution corresponds to a supported non-dominated point in the objective space of the minsum–maxmin bicriteria path problem. This result allows us to design a label setting algorithm which improves all existing algorithms in the state-of-the-art, as it is shown in the extensive experiments carried out considering synthetic and real networks.