Algorithmica
Volume 51, Number 4, 428-434, DOI: 10.1007/s00453-007-9063-0

An O ( n 3(log log  n /log  n )5/4) Time Algorithm for All Pairs Shortest Path

Yijie Han

View Related Documents

Abstract

We present an O(n 3(log log n/log n)5/4) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n 3/log n) time.

Keywords  Algorithms - Complexity - Graph algorithms - Shortest path

Research supported in part by NSF grant 0310245.

Fulltext Preview

Image of the first page of the fulltext document