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[]
- Uri Zwick. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 3 (May 2002), 289–317.
- Liam Roditty and Asaf Shapira. 2008. All-Pairs Shortest Paths with a Sublinear Additive Error. ICALP '08, Part I, LNCS 5125, pp. 622–633, 2008.
See also[]
Categories:
- Combinatorics stubs
- Graph products
- Graph distance