Min-plus matrix multiplication
Min-plus matrix multiplication, also known as the distance product, is an operation on matrices.
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.
- 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.
- Floyd–Warshall algorithm
- Tropical geometry: The distance product is equivalent to standard matrix multiplication in the tropical semi-ring.