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

matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

. 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 In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between t ...

. If

W

is an

n \times n

matrix containing the edge weights of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

, then

W^k

gives the distances between vertices using paths of length at most

k

edges, and

W^n

is the

distance matrix In mathematics, computer science and especially graph theory, a distance matrix is a square matrix In mathematics, a square matrix is a matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of orde ...

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.

References

See also