Min-plus matrix multiplication, also known as distance product, is an operation on matrices.
Given two matrices and , their distance product is defined as an matrix such that . This is standard matrix multiplication for the semi-ring of tropical numbers in the min convention.
This operation is closely related to the shortest path problem. If is an matrix containing the edge weights of a graph, then gives the distances between vertices using paths of length at most edges, and is the distance matrix of the graph.
References Uri Zwick. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 3 (May 2002), 289–317. Liam Roditty and Asaf Shapira. 2008. All-Pairs Shortest Paths with a Sublinear Additive Error. ICALP '08, Part I, LNCS 5125, pp. 622–633, 2008.
See also