Min-plus matrix multiplication

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

Given two $n \times n$ matrices A = (a_ij) and B = (b_ij), their distance product $C = (c_{ij}) = A \star B$ is defined as an $n \times n$ matrix such that $c_{ij} = \min_{k=1}^n \{a_{ik} + b_{kj}\}$.

This operation is closely related to the shortest path problem. If W is an $n \times n$ matrix containing the edge weights of a graph, then W^k is gives the distances between vertices using paths of length at most k edges, and Wⁿ 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: The distance product is equivalent to standard matrix multiplication in the tropical semi-ring.