Min-plus matrix multiplication

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

Given two ${\displaystyle n\times n}$ matrices ${\displaystyle A=(a_{ij})}$ and ${\displaystyle B=(b_{ij})}$, their distance product ${\displaystyle C=(c_{ij})=A\star B}$ is defined as an ${\displaystyle n\times n}$ matrix such that ${\displaystyle c_{ij}=\min _{k=1}^{n}\{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 ${\displaystyle W}$ is an ${\displaystyle n\times n}$ matrix containing the edge weights of a graph, then ${\displaystyle W^{k}}$ gives the distances between vertices using paths of length at most ${\displaystyle k}$ edges, and ${\displaystyle 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