An O(n~3 log log n/ log n) time algorithm for the all-pairs shortest path problem

摘要

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.