The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We propose a new p-processor BSP algorithm for the all-pairs shortest paths problem in a weighted directed dense graph. In contrast with the general algebraic path algorithm, which performs O(p1/2) to O(p2/3) global synchronisation steps, our new algorithm only requires O(log p) synchronisation steps. © 2011 Springer-Verlag Berlin Heidelberg.