Min-plus matrix multiplication

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2024) (Learn how and when to remove this message)

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.

• 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.

• Floyd–Warshall algorithm
• Tropical geometry

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e