A more efficient algorithm for the min-plus multiplication
Włodzimierz Dobosiewicz · International Journal of Computer Mathematics · 1990
The (min, + ) product C of two n × n matrices A and B is defined as C ij = min1≦k≦n A ik + B kj . This paper presents an algorithm to compute the (min, +) product of two n × n matrices. The algorithm follows the approach described by Fredman, but is faster than Fredman's own algorithm: its time complexity is either O(n 3/√log2 n) or even O(n 2.5√log2 n), if one adheres to the uniform-cost RAM model faithfully. This result implies the existence of O(n 3/√log2 n) algorithms for the problems that (min, +) matrix multiplication is equivalent to, such as the all-pairs shortest paths problem. As the presented algorithm uses operations on sets, the formal analysis of its time complexity raises a few interesting questions about the applicability of the standard RAM complexity model.