Academic Research Library

Find some of the best Journals and Proceedings.

An improvement to Floyd-Warshall’s all pairs shortest paths algorithm on certain classes of graphs

Author : Giuseppe Lancia

Abstract :The famous Floyd-Warshall’s algorithm is a cubic procedure to compute all shortest path distances in a complete graph of n nodes. FW procedure revisits n times all the cells of an n×n distance matrix. At each pass, all the cells are considered but only some of them get updated. In this work, we describe a new version of the algorithm which can avoid the consideration of cells which will not be updated, thus reducing the overall running time. Our procedure employes heap data-structures to quickly identify which cells are good candidates for an update. By using suitable heaps, we can choose “good” cells to sample, instead of considering them all like FW does. Our version is better than FW for input graphs in which the number of cells updated over all passes is substantially smaller than the number of checks. For graphs in which the ratio between cell checks and updates is not large enough, we propose a hybrid combination of the new and old approaches, starting with the original FW and then switching to our version after some iterations. Preliminary experiments show the effectiveness of this strategy, with speed-ups from 3 to 10+ times

Keywords :Floyd-Warshall Algorithm, Shortest Paths, Graph Optimization, Heap Data Structures, Runtime Efficiency

Conference Name :International Symposium on Mathematics and Computer Science (ISMCS-25)

Conference Place New York USA

Conference Date 20th Aug 2025

Preview