min-plus matrix multiplication

{{No footnotes|date=November 2024}}

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

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