https://doi.org/10.1140/epjds/s13688-025-00542-0
Research
Assessing the complexity of a path search optimization method based on clustering for a transport graph
1
MIPT (Moscow Institute of Physics and Technology), Moscow, Russia
2
Sber AI Lab, Moscow, Russia
3
ITMO University, St. Petersburg, Russia
4
Learning Planet Institute, Cergy University, Paris, France
5
Sber AI, Moscow, Russia
6
Artificial Intelligence Research Institute (AIRI), Moscow, Russia
Received:
28
August
2024
Accepted:
17
March
2025
Published online:
17
April
2025
Finding the shortest path between two vertices in a graph is essential in various applications, including logistics, social networks, citation graphs, and others. Given the need for repeated pathfinding in large graphs, accelerating this process is crucial. This article introduces a novel method that leverages the inherent clustering of graphs, enabling a quick elimination of suboptimal routes and significantly enhancing efficiency with minimal accuracy losses. Our approach builds upon traditional algorithms, such as the bidirectional Dijkstra, and explores hierarchical techniques. Extensive testing on over 750 real-world city graphs – including those of Beijing, Moscow, Paris, Barcelona, and New York – demonstrates its effectiveness. This article provides a comprehensive overview of the proposed method and its performance statistics.
Key words: Human mobility / Pathfinding optimization / Clustering pathfinding / Analytical complexity assessment
Supplementary Information The online version contains supplementary material available at https://doi.org/10.1140/epjds/s13688-025-00542-0.
© The Author(s) 2025
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
