Min-plus matrix multiplication

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

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

• Graph products
• Graph distance
• Graph theory stubs

• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from November 2024
• All articles lacking in-text citations
• All stub articles