Floyd–Warshall algorithm for sparse graphs

Zugan, Dani (author), Požar, Rok (author), Brodnik, Andrej (author)

The Floyd–Warshall 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’s, 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.

• Language: English
• Keywords: Floyd–Warshall algorithm, all-pairs shortest paths, sparse graphs, strongly connected components
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: 13 str.
• Numbering: Vol. 18, iss. 12, art. 766
• PID: 20.500.12556/RUL-177565
• UDC: 004:519.85
• ISSN on article: 1999-4893
• DOI: 10.3390/a18120766
• COBISS.SI-ID: 262471683
• Publication date in RUL: 24.12.2025

Record is a part of a journal

• Title: Algorithms
• Shortened title: Algorithms
• Publisher: MDPI
• ISSN: 1999-4893
• COBISS.SI-ID: 517501977

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: Floyd–Warshallov algoritem, najkrajše poti med vsemi pari vozlišč, redki grafi, močno povezane komponente, Kruskalov algoritem