1 Answers
Min-plus matrix multiplication, also known as distance product, is an operation on matrices.
Given two n × n {\displaystyle n\times n} matrices A = {\displaystyle A=} and B = {\displaystyle B=} , their distance product C = = A ⋆ B {\displaystyle C==A\star B} is defined as an n × n {\displaystyle n\times n} matrix such that c i j = min k = 1 n { a i k + b k j } {\displaystyle c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}}. 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. If W {\displaystyle W} is an n × n {\displaystyle n\times n} matrix containing the edge weights of a graph, then W k {\displaystyle W^{k}} gives the distances between vertices using paths of length at most k {\displaystyle k} edges, and W n {\displaystyle W^{n}} is the distance matrix of the graph.