Assessing the complexity of a path search optimization method based on clustering for a transport graph

Abstract

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.