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.

References

See also

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.