R-Kleene: A high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks

We propose a novel divide-and-conquer algorithm for the solution of the all-pair shortest-path problem for directed and dense graphs with no negative cycles. We propose R-Kleene, a compact and in-place recursive algorithm inspired by Kleene's algorithm. R-Kleene delivers a better performance than previous algorithms for randomly generated graphs represented by highly dense adjacency matrices, in which the matrix components can have any integer value. We show that R-Kleene, unchanged and without any machine tuning, yields consistently between (1)/(7) and (1)/(2) of the peak performance running on five very different uniprocessor systems.