Title :
An all pairs shortest path algorithm with expected running time O(n 2logn)
Author :
Moffat, Alistair ; Takaoka, Tadao
Abstract :
An algorithm is described that solves the all pairs shortest path problem for a nonnegatively weighted graph. The algorithm has an average requirement on quite general classes of random graphs of O(n2logn) time, where n is the number of vertices in the graph.
Keywords :
Algorithm design and analysis; Computer science; Cost function; Data structures; Information science; Shortest path problem; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1985., 26th Annual Symposium on
Conference_Location :
Portland, OR, USA
Print_ISBN :
0-8186-0644-4
DOI :
10.1109/SFCS.1985.6
