Treffer: 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. [ABSTRACT FROM AUTHOR]

Copyright of Algorithms is the property of MDPI and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)