This paper achieves O(n(3) log log n/ log n) time for the all pairs shortest path problem on the conventional RAM model where only arithmetic operations, branching operations, and random accessibility with O(log n) bits are allowed. (c) 2005 Elsevier B.V. All rights reserved.