20.500.12556/RUL-177565 Floyd–Warshall algorithm for sparse graphs 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. Floyd–Warshall algorithm all-pairs shortest paths sparse graphs strongly connected components Floyd–Warshallov algoritem najkrajše poti med vsemi pari vozlišč redki grafi močno povezane komponente Kruskalov algoritem true false true Angleški jezik Slovenski jezik Neznano 2025-12-24 09:00:39 2025-12-24 09:00:40 2026-01-02 03:55:14 0000-00-00 00:00:00 2025 0 0 13 str. iss. 12, art. 766 Vol. 18 Dec. 2025 0000-00-00 Zaloznikova Objavljeno apc 0000-00-00 0000-00-00 0000-00-00 004:519.85 1999-4893 10.3390/a18120766 262471683 RAZ_Zugan_Dani_2025.pdf RAZ_Zugan_Dani_2025.pdf 1 19A996B2BBA4664FD2BAADE54F9E5468 679c54d3b61ac4820396c0946e9600b1e17963772bafde951bbd80b37c3fc9aa 265802af-e09f-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=224640 https://www.mdpi.com/1999-4893/18/12/766 1 2f9481dc-e09e-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=224638 Fakulteta za računalništvo in informatiko 0 0 0