Умножение матрицы мин-плюс

Умножение матриц мин-плюс , также известное как произведение расстояний , представляет собой операцию над матрицами .

Учитывая два $n\times n$ матрицы $A=(a_{ij})$ и $B=(b_{ij})$ , их произведение расстояний $C=(c_{ij})=A\star B$ определяется как $n\times n$ матрица такая, что $c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}$ . Это стандартное матричное умножение полукольца тропических чисел в соглашении о минимуме.

Эта операция тесно связана с задачей поиска кратчайшего пути . Если $W$ это $n\times n$ матрица, содержащая веса ребер графа , то $W^{k}$ дает расстояния между вершинами, используя пути максимальной длины $k$ края, и $W^{n}$ - матрица расстояний графа.