Min plus matrix multiplication

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

Given two n × n matrices A = ( a i j ) and B = ( b i j ) , their distance product C = ( c i j ) = A ⋆ B is defined as an n × n matrix such that c i j = min k = 1 n { a i k + b k j } .

This operation is closely related to the shortest path problem. If W is an n × 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.