NEW IDEAS TO SPEED-UP FLOYD-WARSHALL SHORTEST PATHS ALGORITHM

Floyd and Warshall’s algorithm for the all-pairs shortest path problem is a Θ(n3) procedure which revisits n times all the cells of an n×n distance matrix. At each pass, all the cells are checked but only some of them get updated. In this paper, we report some preliminary results on a new version of the algorithm, designed to avoid checking cells which will not be updated, in order to reduce the overall time. Our procedure uses heaps to quickly identify which cells can be good candidates for an update. The new version improves over Floyd-Warshall’s original for those input graphs in which the number of cells updated over all passes is substantially smaller than the number of checks. However, our procedure is worse than the original if the ratio between cell checks and updates is not large enough. To obtain an improvement independently of the particular instance type, we propose a hybrid combination of the two approaches, which starts with the original Floyd and Warshall version and then switches to the new one after some iterations. Preliminary experiments show the effectiveness of this strategy