Floyd–Warshall algorithm for sparse graphs

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

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.

• Jezik: Angleški jezik
• Ključne besede: Floyd–Warshall algorithm, all-pairs shortest paths, sparse graphs, strongly connected components
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: 13 str.
• Številčenje: Vol. 18, iss. 12, art. 766
• PID: 20.500.12556/RUL-177565
• UDK: 004:519.85
• ISSN pri članku: 1999-4893
• DOI: 10.3390/a18120766
• COBISS.SI-ID: 262471683
• Datum objave v RUL: 24.12.2025

Gradivo je del revije

• Naslov: Algorithms
• Skrajšan naslov: Algorithms
• Založnik: MDPI
• ISSN: 1999-4893
• COBISS.SI-ID: 517501977

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: Floyd–Warshallov algoritem, najkrajše poti med vsemi pari vozlišč, redki grafi, močno povezane komponente, Kruskalov algoritem