Min-plus matrix multiplication
Min-plus matrix multiplication, also known as distance product, is an operation on matrices.
Given two matrices and, their distance product is defined as an matrix such that. 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 is an matrix containing the edge weights of a graph, then gives the distances between vertices using paths of length at most edges, and is the distance matrix of the graph.
