A Note on Spira’s Algorithm for the All-Pairs Shortest-Path Problem
John S. Carson, Averill M. Law · SIAM Journal on Computing · 1977
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.