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

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

.

Given two matrices and , their distance product is defined as an matrix such that .

This operation is closely related to the shortest path problem

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...

. If is an matrix containing the edge weights of a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

, then is gives the distances between vertices using paths of length at most edges, and is the distance matrix

Distance matrix

In mathematics, computer science and graph theory, a distance matrix is a matrix containing the distances, taken pairwise, of a set of points...

 of the graph.

See also

• Floyd-Warshall algorithm
  Floyd-Warshall algorithm
  In computer science, the Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph and also for finding transitive closure of a relation R...
  
  
• Tropical geometry
  Tropical geometry
  Tropical geometry is a relatively new area in mathematics, which might loosely be described as a piece-wise linear or skeletonized version of algebraic geometry. Its leading ideas had appeared in different guises in previous works of George M...
  
  : The distance product is equivalent to standard matrix multiplication in the tropical semi-ring.