Min-plus matrix multiplication

From formulasearchengine
Jump to navigation Jump to search

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

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

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.

References

See also

Template:Combin-stub