Min-plus matrix multiplication

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

Given two $n \times n$ matrices $A = (a_{ij})$ and $B = (b_{ij})$ , their distance product $C = (c_{ij}) = A \star B$ is defined as an $n \times n$ matrix such that $c_{ij} = \min_{k=1}^n \{a_{ik} + b_{kj}\}$ .

This operation is closely related to the shortest path problem. If $W$ is an $n \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.