We describe an O(n3/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, Takaoka, Dobosiewicz, Han and Zwick. The new algorithm is surprisingly simple and different from previous ones.
