Loading AI tools
From Wikipedia, the free encyclopedia
Min-plus matrix multiplication, also known as distance product, is an operation on matrices.
Given two matrices and , their distance product is defined as an matrix such that . 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 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.