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

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.

Citation metrics