min-plus matrix multiplication

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

Given two $n \times n$ matrices $A = (a_)$ and $B = (b_)$, their distance product $C = (c_) = A \star B$ is defined as an $n \times n$ matrix such that $c_ = \min_^n \$. 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 $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.

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

* Floyd–Warshall algorithm
* Tropical geometry

Graph products
Graph distance

{{graph-stub