Abstract A mean‐time comparison of the algorithms of Floyd, Dantzig, Tabourier, and of repeated application of several single‐source algorithms, for the all‐pairs shortest‐path problem with arbitrary arc lengths clearly demonstrates the superiority of the Tabourier procedure for networks in which an average of at least 25% of the potential direct arcs are present. For very sparse networks, repeated application of a single‐source label‐correcting algorithm is found to be preferable.

We correct some errors in Spira’s algorithm for the all-pairs shortest-path problem, and empirically compare his algorithm (with two distinct sorting, routines) to Dijkstra’s procedure. The results show that Spira’s algorithm is only efficient for “large” networks. Furthermore, it is seen that the asymptotic number of additions and comparisons required by two algorithms may be a very poor indicator of their relative running times.