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.