# Fast One-to-Many Multicriteria Shortest Path Search

arXiv: https://arxiv.org/abs/2201.12684 · HTML: https://mlsanity.com/paper/2201.12684/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2022.

## Built on by (most cited first, 2 of 2)

- [Multi-Objective Search: Algorithms, Applications, and Emerging Directions](https://mlsanity.com/paper/2510.25504/) (2025)
- [LegalFarePlan: A Label-Setting Framework for Fare-Transparent Urban Rail Route Planning under Non-Additive Fare Rules](https://mlsanity.com/paper/2607.09755/) (2026)

## Abstract (arXiv)

This paper introduces a novel algorithm combination designed for fast one-to-many multicriteria shortest path search. A preprocessing algorithm excludes irrelevant vertices by building a smaller cover graph. A modified version of multicriteria label-setting algorithm operates on the cover graph and employs a dimensionality reduction technique for swifter domination checks. While the method itself maintains solution optimality, it is able to additionally incorporate existing heuristics for further speedups. The proposed algorithm has been tested on multiple criteria combinations of varying correlation. The results show the introduced approach provides a speedup of at least 6 times on simple criteria combinations and up to 60 times on hard instances compared to vanilla multicriteria label-setting. Graph preprocessing also decreases memory requirements of queries by up to 13 times.