Min-plus matrix multiplication explained

Min-plus matrix multiplication, also known as distance product, is an operation on matrices.

Given two

n x n matrices A = (a _{ij} ) and B = (b _{ij} ) , their distance product C = (c _{ij} ) = A \star B is defined as an n x n matrix such that c _{ij} = min ^{n} _{k =1} \{a _{ik} + b _{kj} \} . 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

W is an n x n matrix containing the edge weights of a graph, then W ^{k} gives the distances between vertices using paths of length at most k edges, and W ^{n} 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

• Floyd–Warshall algorithm
• Tropical geometry