Min-plus matrix multiplication

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

Given two n \times n matrices A = (a_{ij}) and B = (b_{ij}), their distance product C = (c_{ij}) = A \star B is defined as an n \times n matrix such that c_{ij} = \min_{k=1}^n \{a_{ik} + b_{kj}\}.

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

See also

This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.