Lecture Notes in Computer Science, 2005, Volume 3608/2005, 318-324, DOI: 10.1007/11534273_28

All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time

Timothy M. Chan

View Related Documents

Abstract

We describe an O(n 3/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.

Fulltext Preview

Image of the first page of the fulltext document