{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T05:24:42Z","timestamp":1764998682843,"version":"3.46.0"},"reference-count":23,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T00:00:00Z","timestamp":1764806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ARIS","award":["P2-0359","P1-0285","N1-0159","J1-2451","N1-0209","J5-4596"],"award-info":[{"award-number":["P2-0359","P1-0285","N1-0159","J1-2451","N1-0209","J5-4596"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Floyd\u2013Warshall algorithm, which uses a classic dynamic programming approach, provides a solution to the all-pairs shortest paths problem. However, for sparse graphs, iteratively applying Dijkstra\u2019s, or some other similar algorithm from each node, often proves to be more efficient. We introduce a novel technique based on a structural decomposition of the input graph into strongly connected components, allowing us to exploit the disconnectedness of the graph by avoiding redundant relaxation attempts on nodes that are not reachable from the source component. Using an empirical evaluation, where execution time is measured, we demonstrate that our approach outperforms existing alternatives on disconnected graphs.<\/jats:p>","DOI":"10.3390\/a18120766","type":"journal-article","created":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T18:42:02Z","timestamp":1764960122000},"page":"766","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Floyd\u2013Warshall Algorithm for Sparse Graphs"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8819-2538","authenticated-orcid":false,"given":"Dani","family":"Zugan","sequence":"first","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, 1000 Ljubljana, Slovenia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2037-9535","authenticated-orcid":false,"given":"Rok","family":"Po\u017ear","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, 6000 Koper, Slovenia"},{"name":"Andrej Maru\u0161i\u010d Institute, University of Primorska, 6000 Koper, Slovenia"},{"name":"Institute of Mathematics, Physics and Mechanics, 1000 Ljubljana, Slovenia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9773-0664","authenticated-orcid":false,"given":"Andrej","family":"Brodnik","sequence":"additional","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, 1000 Ljubljana, Slovenia"},{"name":"Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, 6000 Koper, Slovenia"},{"name":"Andrej Maru\u0161i\u010d Institute, University of Primorska, 6000 Koper, Slovenia"}]}],"member":"1968","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"ref_1","unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory, Algorithms and Applications, Prentice-Hall, Inc."},{"key":"ref_2","first-page":"27","article-title":"Random Graph Dynamics","volume":"Volume 5","author":"Durrett","year":"2006","journal-title":"Cambridge Series in Statistical and Probabilistic Mathematics"},{"key":"ref_3","first-page":"290","article-title":"On random graphs I","volume":"6","year":"1959","journal-title":"Publ. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of Scaling in Random Networks","volume":"286","author":"Albert","year":"1999","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: Shortest path","volume":"5","author":"Floyd","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","article-title":"A theorem on boolean matrices","volume":"9","author":"Warshall","year":"1962","journal-title":"J. ACM"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.26493\/1855-3974.2467.497","article-title":"Modifications of the Floyd\u2013Warshall algorithm with nearly quadratic expected-time","volume":"22","author":"Brodnik","year":"2021","journal-title":"Ars Math. Contemp."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Lancia, G., and Dalpasso, M. (2025). Speeding Up Floyd\u2013Warshall\u2019s Algorithm to Compute All-Pairs Shortest Paths and the Transitive Closure of a Graph. Algorithms, 18.","DOI":"10.3390\/a18090560"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.aml.2011.06.008","article-title":"Speeding up the Floyd\u2013Warshall algorithm for the cycled shortest path problem","volume":"25","author":"Aini","year":"2012","journal-title":"Appl. Math. Lett."},{"key":"ref_10","first-page":"1287","article-title":"The Floyd\u2013Warshall all-pairs shortest paths algorithm for disconnected and very sparse graphs","volume":"53","author":"Toroslu","year":"2023","journal-title":"Software: Pract. Exp."},{"key":"ref_11","first-page":"31","article-title":"A Performance Comparison of Shortest Path Algorithms in Directed Graphs","volume":"100","author":"Sapundzhi","year":"2025","journal-title":"Eng. Proc."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01840439","article-title":"The pairing heap: A new form of self-adjusting heap","volume":"1","author":"Fredman","year":"1986","journal-title":"Algorithmica"},{"key":"ref_15","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press. [3rd ed.]."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1137\/0222071","article-title":"Finding the hidden path: Time bounds for all-pairs shortest paths","volume":"22","author":"Karger","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1145\/1039488.1039492","article-title":"A new approach to dynamic all pairs shortest paths","volume":"51","author":"Demetrescu","year":"2004","journal-title":"J. ACM"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1145\/1198513.1198519","article-title":"Experimental analysis of dynamic all pairs shortest path algorithms","volume":"2","author":"Demetrescu","year":"2006","journal-title":"ACM Trans. Algorithms"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","article-title":"Log-Logarithmic Worst-Case Range Queries are Possible in Space \ud835\udcaa(n)","volume":"17","author":"Willard","year":"1983","journal-title":"Inf. Process. Lett."},{"key":"ref_20","unstructured":"Leskovec, J., and Krevl, A. (2025, May 13). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: https:\/\/snap.stanford.edu\/data\/#p2p."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1109\/4236.978369","article-title":"Mapping the Gnutella network: Properties of large-scale peer-to-peer systems and implications for system design","volume":"6","author":"Ripeanu","year":"2002","journal-title":"IEEE Internet Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"103815","DOI":"10.1016\/j.ejc.2023.103815","article-title":"Finding strong components using depth-first search","volume":"119","author":"Tarjan","year":"2024","journal-title":"Eur. J. Comb."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/12\/766\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T05:20:01Z","timestamp":1764998401000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/12\/766"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":23,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["a18120766"],"URL":"https:\/\/doi.org\/10.3390\/a18120766","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}