Speeding Up Floyd–Warshall’s Algorithm to Compute All-Pairs Shortest Paths and the Transitive Closure of a Graph
Open Access
- 4 September 2025
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 18 (9) , 560
Abstract
Floyd–Warshall’s algorithm is a widely-known procedure for computing all-pairs shortest paths in a graph of n vertices in time complexity. A simplified version of the same algorithm computes the transitive closure of the graph with the same time complexity. The algorithm operates on an matrix, performing n inspections and no more than n updates of each matrix cell, until the final matrix is computed. In this paper, we apply a technique called SmartForce, originally devised as a performance enhancement for solving the traveling salesman problem, to avoid the inspection and checking of cells that do not need to be updated, thus reducing the overall computation time when the number, u, of cell updates is substantially smaller than . When the ratio is not small enough, the performance of the proposed procedure might be worse than that of the Floyd–Warshall algorithm. To speed up the algorithm independently of the input instance type, we introduce an effective hybrid approach. Finally, a similar procedure, which exploits suitable fast data structures, can be used to achieve a speedup over the Floyd–Warshall simplified algorithm that computes the transitive closure of a graph.
Keywords
This publication has 14 references indexed in Scilit:
- Algorithmic strategies for a fast exploration of the TSP $4$-OPT neighborhoodJournal of Heuristics, 2023
- Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-timeArs Mathematica Contemporanea, 2021
- Finding the largest triangle in a graph in expected quadratic timeEuropean Journal of Operational Research, 2020
- FASTSET: A Fast Data Structure for the Representation of Sets of IntegersAlgorithms, 2019
- An O(n 3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest PathAlgorithmica, 2007
- On the All-Pairs-Shortest-Path Problem in Unweighted Undirected GraphsJournal of Computer and System Sciences, 1995
- New Bounds on the Complexity of the Shortest Path ProblemSIAM Journal on Computing, 1976
- Algorithm 97: Shortest pathCommunications of the ACM, 1962
- A Theorem on Boolean MatricesJournal of the ACM, 1962
- On a routing problemQuarterly of Applied Mathematics, 1958