{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:52:48Z","timestamp":1774680768815,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["EPJ Data Sci."],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>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 \u2013 including those of Beijing, Moscow, Paris, Barcelona, and New York \u2013 demonstrates its effectiveness. This article provides a comprehensive overview of the proposed method and its performance statistics.<\/jats:p>","DOI":"10.1140\/epjds\/s13688-025-00542-0","type":"journal-article","created":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T13:56:07Z","timestamp":1744898167000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Assessing the complexity of a path search optimization method based on clustering for a transport graph"],"prefix":"10.1140","volume":"14","author":[{"given":"Dmitrii","family":"Fedorov","sequence":"first","affiliation":[]},{"given":"Georgii","family":"Kontsevik","sequence":"additional","affiliation":[]},{"given":"Roman","family":"Bashirov","sequence":"additional","affiliation":[]},{"given":"Sergey","family":"Mityagin","sequence":"additional","affiliation":[]},{"given":"Liubov","family":"Tupikina","sequence":"additional","affiliation":[]},{"given":"Nikita","family":"Zakharenko","sequence":"additional","affiliation":[]},{"given":"Semen","family":"Budennyy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,17]]},"reference":[{"issue":"10","key":"542_CR1","doi-asserted-by":"publisher","first-page":"2244","DOI":"10.1016\/j.dam.2008.06.035","volume":"157","author":"FJ Planes","year":"2009","unstructured":"Planes FJ, Beasley JE (2009) Path finding approaches and metabolic pathways. Discrete Appl Math 157(10):2244\u20132256. https:\/\/doi.org\/10.1016\/j.dam.2008.06.035. Networks in Computational Biology","journal-title":"Discrete Appl Math"},{"key":"542_CR2","unstructured":"Madkour A, Aref WG, Rehman FU, Rahman MA, Basalamah S (2017) A survey of shortest-path algorithms. arXiv preprint arXiv:1705.02044"},{"key":"542_CR3","first-page":"568","volume-title":"Highway hierarchies hasten exact shortest path queries","author":"P Sanders","year":"2005","unstructured":"Sanders P, Schultes D (2005) In: Brodal GS, Leonardi S (eds) Highway hierarchies hasten exact shortest path queries. Springer, Berlin, pp\u00a0568\u2013579"},{"key":"542_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.5","volume-title":"Proceedings of the 9th workshop on algorithm engineering and experiments and the 4th workshop on analytic algorithms and combinatorics","author":"H Bast","year":"2007","unstructured":"Bast H, Funke S, Matijevic D, Sanders P, Schultes D (2007) In transit to constant time shortest-path queries in road networks. In: Proceedings of the 9th workshop on algorithm engineering and experiments and the 4th workshop on analytic algorithms and combinatorics. https:\/\/doi.org\/10.1137\/1.9781611972870.5"},{"key":"542_CR5","series-title":"Proceedings","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-540-68552-4_24","volume-title":"Experimental algorithms: 7th international workshop, WEA 2008","author":"R Geisberger","year":"2008","unstructured":"Geisberger R, Sanders P, Schultes D, Delling D (2008) Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: Experimental algorithms: 7th international workshop, WEA 2008, Provincetown, MA, USA, May 30-June 1, 2008, Proceedings, vol\u00a07. Springer, Berlin, pp\u00a0319\u2013333"},{"key":"542_CR6","doi-asserted-by":"publisher","unstructured":"Geisberger R, Sanders P, Schultes D, Vetter C (2012) Exact routing in large road networks using contraction hierarchies. Transp Sci 46. https:\/\/doi.org\/10.1287\/trsc.1110.0401","DOI":"10.1287\/trsc.1110.0401"},{"key":"542_CR7","doi-asserted-by":"publisher","DOI":"10.1145\/2886843","volume":"21","author":"J Dibbelt","year":"2016","unstructured":"Dibbelt J, Strasser B, Wagner D (2016) Customizable contraction hierarchies. ACM J Exp Algorithmics 21:1.5. https:\/\/doi.org\/10.1145\/2886843","journal-title":"ACM J Exp Algorithmics"},{"key":"542_CR8","volume":"14","author":"J Maue","year":"2010","unstructured":"Maue J, Sanders P, Matijevic D (2010) Goal-directed shortest-path queries using precomputed cluster distances. ACM J Exp Algorithmics 14:3.2","journal-title":"ACM J Exp Algorithmics"},{"key":"542_CR9","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976","volume":"15","author":"R Bauer","year":"2010","unstructured":"Bauer R, Delling D, Sanders P, Schieferdecker D, Schultes D, Wagner D (2010) Combining hierarchical and goal-directed speed-up techniques for Dijkstra\u2019s algorithm. ACM J Exp Algorithmics 15:2.3","journal-title":"ACM J Exp Algorithmics"},{"key":"542_CR10","volume-title":"Community detection in the hyperbolic space","author":"M Bruno","year":"2019","unstructured":"Bruno M, Ferreira S, Gursoy F, Serafino M, Vianello F, Vranic A, Bogu\u00f1\u00e1 M (2019) Community detection in the hyperbolic space"},{"key":"542_CR11","doi-asserted-by":"publisher","unstructured":"Cohen E, Halperin E, Kaplan H, Zwick U (2003) Reachability and distance queries via 2-hop labels. SIAM J Comput 32. https:\/\/doi.org\/10.1137\/S0097539702403098","DOI":"10.1137\/S0097539702403098"},{"key":"542_CR12","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930","volume-title":"SIGMOD-PODS\u201909 - proceedings of the international conference on management of data and 28th symposium on principles of database systems","author":"R Jin","year":"2009","unstructured":"Jin R, Xiang Y, Ruan N, Fuhry D (2009) 3-hop: a high-compression indexing scheme for reachability query. In: SIGMOD-PODS\u201909 - proceedings of the international conference on management of data and 28th symposium on principles of database systems. https:\/\/doi.org\/10.1145\/1559845.1559930"},{"key":"542_CR13","series-title":"Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics)","volume-title":"Hierarchical hub labelings for shortest paths","author":"I Abraham","year":"2012","unstructured":"Abraham I, Delling D, Goldberg AV, Werneck RF (2012) Hierarchical hub labelings for shortest paths. Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), vol\u00a07501, LNCS. Springer, Berlin"},{"key":"542_CR14","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887","volume-title":"Proceedings of the ACM SIGMOD international conference on management of data","author":"R Jin","year":"2012","unstructured":"Jin R, Ruan N, Xiang Y, Lee V (2012) A highway-centric labeling approach for answering distance queries on large sparse graphs. In: Proceedings of the ACM SIGMOD international conference on management of data. https:\/\/doi.org\/10.1145\/2213836.2213887"},{"key":"542_CR15","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1007\/s00778-023-00789-x","volume":"32","author":"D Ouyang","year":"2023","unstructured":"Ouyang D, Wen D, Qin L, Chang L, Lin X, Zhang Y (2023) When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries on road networks. VLDB J 32:1263\u20131287. https:\/\/doi.org\/10.1007\/s00778-023-00789-x","journal-title":"VLDB J"},{"key":"542_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1187436.1216585","volume":"11","author":"RH M\u00f6hring","year":"2007","unstructured":"M\u00f6hring RH, Schilling H, Sch\u00fctz B, Wagner D, Willhalm T (2007) Partitioning graphs to speedup Dijkstra\u2019s algorithm. ACM J Exp Algorithmics 11:2\u20138","journal-title":"ACM J Exp Algorithmics"},{"key":"542_CR17","first-page":"117","volume-title":"Recent advances in graph partitioning","author":"A Bulu\u00e7","year":"2016","unstructured":"Bulu\u00e7 A, Meyerhenke H, Safro I, Sanders P, Schulz C (2016) In: Kliemann L, Sanders P (eds) Recent advances in graph partitioning. Springer, Cham, pp\u00a0117\u2013158"},{"issue":"1","key":"542_CR18","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/s10796-021-10164-2","volume":"24","author":"B Tesfaye","year":"2022","unstructured":"Tesfaye B, Augsten N, Pawlik M, B\u00f6hlen MH, Jensen CS (2022) Speeding up reachability queries in public transport networks using graph partitioning. Inf Syst Front 24(1):11\u201329","journal-title":"Inf Syst Front"},{"key":"542_CR19","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.neucom.2021.01.068","volume":"439","author":"H Xu","year":"2021","unstructured":"Xu H, Duan Z, Wang Y, Feng J, Chen R, Zhang Q, Xu Z (2021) Graph partitioning and graph neural network based hierarchical graph matching for graph similarity computation. Neurocomputing 439:348\u2013362","journal-title":"Neurocomputing"},{"key":"542_CR20","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/2213836.2213855","volume-title":"Proceedings of the 2012 ACM SIGMOD international conference on management of data. SIGMOD \u201912","author":"W Fan","year":"2012","unstructured":"Fan W, Li J, Wang X, Wu Y (2012) Query preserving graph compression. In: Proceedings of the 2012 ACM SIGMOD international conference on management of data. SIGMOD \u201912. Assoc. Comput. Mach., New York, pp\u00a0157\u2013168. https:\/\/doi.org\/10.1145\/2213836.2213855"},{"issue":"4","key":"542_CR21","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1089\/cmb.2019.0324","volume":"27","author":"M Karasikov","year":"2020","unstructured":"Karasikov M, Mustafa H, Joudaki A, Javadzadeh-no S, R\u00e4tsch G, Kahles A (2020) Sparse binary relation representations for genome graph annotation. J Comput Biol 27(4):626\u2013639. https:\/\/doi.org\/10.1089\/cmb.2019.0324. PMID: 31891531","journal-title":"J Comput Biol"},{"issue":"1","key":"542_CR22","doi-asserted-by":"publisher","DOI":"10.1140\/epjds\/s13688-018-0160-x","volume":"7","author":"B Monechi","year":"2018","unstructured":"Monechi B, Gravino P, Di Clemente R, Servedio VD (2018) Complex delay dynamics on railway networks from universal laws to realistic modelling. EPJ Data Sci 7(1):35","journal-title":"EPJ Data Sci"},{"issue":"2","key":"542_CR23","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s42489-023-00138-6","volume":"73","author":"L Tupikina","year":"2023","unstructured":"Tupikina L, Nematollahi Y, Kisseleva O, Afanasiev V, Monechi B (2023) Exploring hidden city patterns with urban walks and citizen science data. KN-J Cartogr Geogr Inf Syst 73(2):109\u2013115","journal-title":"KN-J Cartogr Geogr Inf Syst"},{"issue":"1\u20133","key":"542_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2010.11.002","volume":"499","author":"M Barth\u00e9lemy","year":"2011","unstructured":"Barth\u00e9lemy M (2011) Spatial networks. Phys Rep 499(1\u20133):1\u2013101","journal-title":"Phys Rep"},{"key":"542_CR25","doi-asserted-by":"publisher","DOI":"10.1145\/3626641.3626941","volume-title":"Proceedings of the 8th international conference on sustainable information engineering and technology","author":"A Pinandito","year":"2023","unstructured":"Pinandito A, Kharisma AP, Akbar MA (2023) Improving route-finding performance of Dijkstra algorithm and maintaining path visual cue using Douglas-peucker algorithm. In: Proceedings of the 8th international conference on sustainable information engineering and technology. https:\/\/doi.org\/10.1145\/3626641.3626941"},{"key":"542_CR26","first-page":"59","volume-title":"PG (short papers)","author":"NM Wardhana","year":"2015","unstructured":"Wardhana NM, Johan H, Seah HS (2015) Accelerating graph-based path planning through waypoint clustering. In: PG (short papers), pp\u00a059\u201363"},{"issue":"2","key":"542_CR27","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1109\/TAES.2008.4560197","volume":"44","author":"R Rajagopalan","year":"2008","unstructured":"Rajagopalan R, Mehrotra KG, Mohan CK, Varshney PK (2008) Hierarchical path computation approach for large graphs. IEEE Trans Aerosp Electron Syst 44(2):427\u2013440","journal-title":"IEEE Trans Aerosp Electron Syst"},{"key":"542_CR28","doi-asserted-by":"publisher","unstructured":"Blondel V, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp, 2008. https:\/\/doi.org\/10.1088\/1742-5468\/2008\/10\/P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"542_CR29","doi-asserted-by":"publisher","DOI":"10.1002\/9781118601181.ch13","volume-title":"Multilevel local optimization of modularity","author":"T Aynaud","year":"2013","unstructured":"Aynaud T, Blondel VD, Guillaume JL, Lambiotte R (2013) Multilevel local optimization of modularity. Wiley, New York. https:\/\/doi.org\/10.1002\/9781118601181.ch13"},{"key":"542_CR30","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-319-21042-1_5","volume-title":"Web-age information management","author":"Y Wang","year":"2015","unstructured":"Wang Y, Huang H, Feng C, Liu Z (2015) Community detection based on minimum-cut graph partitioning. In: Dong XL, Yu X, Li J, Sun Y (eds) Web-age information management. Springer, Cham, pp\u00a057\u201369"},{"issue":"12","key":"542_CR31","doi-asserted-by":"publisher","DOI":"10.3390\/math11122702","volume":"11","author":"W Zhu","year":"2023","unstructured":"Zhu W, Li H, Wei W (2023) A two-stage multi-objective evolutionary algorithm for community detection in complex networks. Mathematics 11(12):2702","journal-title":"Mathematics"},{"issue":"3\u20135","key":"542_CR32","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1137\/0110037","volume":"486","author":"S Fortunato","year":"2009","unstructured":"Fortunato S (2009) Community detection in graphs. Phys Rep 486(3\u20135):75\u2013174. https:\/\/doi.org\/10.1137\/0110037","journal-title":"Phys Rep"},{"issue":"4","key":"542_CR33","doi-asserted-by":"publisher","first-page":"477","DOI":"10.21136\/CPM.1955.108220","volume":"80","author":"V Havel","year":"1955","unstructured":"Havel V (1955) A remark on the existence of finite graphs. \u010cas P\u011bst Mat 80(4):477\u2013480. https:\/\/doi.org\/10.21136\/CPM.1955.108220. (in Czech)","journal-title":"\u010cas P\u011bst Mat"},{"issue":"3","key":"542_CR34","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/0110037","volume":"10","author":"SL Hakimi","year":"1962","unstructured":"Hakimi SL (1962) On realizability of a set of integers as degrees of the vertices of a linear graph. I. J Soc Ind Appl Math 10(3):496\u2013506. https:\/\/doi.org\/10.1137\/0110037","journal-title":"J Soc Ind Appl Math"},{"issue":"12","key":"542_CR35","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821\u20137826","journal-title":"Proc Natl Acad Sci"},{"issue":"1","key":"542_CR36","first-page":"261","volume":"12","author":"P Erd\u0151s","year":"1961","unstructured":"Erd\u0151s P, R\u00e9nyi A (1961) On the strength of connectedness of a random graph. Acta Math Hung 12(1):261\u2013267","journal-title":"Acta Math Hung"},{"key":"542_CR37","volume-title":"Scale: the universal laws of life and death in organisms, cities and companies","author":"GB West","year":"2017","unstructured":"West GB (2017) Scale: the universal laws of life and death in organisms, cities and companies. Weidenfeld & Nicolson. https:\/\/books.google.ru\/books?id=PZjCoAEACAAJ"},{"key":"542_CR38","first-page":"118","volume-title":"Doklady mathematics","author":"SA Budennyy","year":"2022","unstructured":"Budennyy SA, Lazarev VD, Zakharenko NN, Korovin AN, Plosskaya O, Dimitrov DV, Akhripkin V, Pavlov I, Oseledets IV, Barsola IS, et al. (2022) Eco2ai: carbon emissions tracking of machine learning models as the first step towards sustainable ai. In: Doklady mathematics, vol\u00a0106. Springer, Berlin, pp\u00a0118\u2013128"}],"container-title":["EPJ Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1140\/epjds\/s13688-025-00542-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1140\/epjds\/s13688-025-00542-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1140\/epjds\/s13688-025-00542-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T13:56:12Z","timestamp":1744898172000},"score":1,"resource":{"primary":{"URL":"https:\/\/epjdatascience.springeropen.com\/articles\/10.1140\/epjds\/s13688-025-00542-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,17]]},"references-count":38,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["542"],"URL":"https:\/\/doi.org\/10.1140\/epjds\/s13688-025-00542-0","relation":{},"ISSN":["2193-1127"],"issn-type":[{"value":"2193-1127","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,17]]},"assertion":[{"value":"28 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"32"}}