Conference Proceedings
An 0(n 2 lognloglogn) expected time algorithm for the all shortest distance problem
T Takaoka, A Moffat
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Published : 1980
DOI: 10.1007/BFb0022539
Abstract
In the present paper we improve Spira's algorithm for the all shortest distance problem and reduce the expected computing time from 0(n2log2n) to 0(n2lognloglogn) where n is the number of vertices in a graph. We also give an algorithm for distance matrix multiplication with 0(n2logn) comparisons and additions between distances where n is the dimension of matrices.