Abstract
We present an \(O(n^3\sqrt{\log\log n}/\!\log n)\)-time algorithm for the All Pairs Shortest Paths (APSP) problem for directed graphs with real edge lengths. This slightly improves previous algorithms for the problem obtained by Fredman, Dobosiewicz, Han, and Takaoka.
Article PDF
Similar content being viewed by others
Use our pre-submission checklist
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zwick, U. A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths. Algorithmica 46, 181–192 (2006). https://doi.org/10.1007/s00453-005-1199-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-005-1199-1