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.