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 tw ...

. 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 (two-dimensional array) containing the distances, taken pairwise, between the elements of a set. Depending upon the application involved, the ''dist ...

of the graph.

References

Uri Zwick Uri Zwick is an Israeli computer scientist and mathematician known for his work on graph algorithms, in particular on distances in graphs and on the color-coding technique for subgraph isomorphism. With Howard Karloff, he is the namesake of the ...

. 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