Умножение матриц мин-плюс - Min-plus matrix multiplication - Wikipedia

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

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

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

Рекомендации

• Ури Цвик. 2002. Все пары кратчайших путей с использованием наборов мостов и умножения прямоугольной матрицы. J. ACM 49, 3 (май 2002 г.), 289–317.
• Лиам Родитти и Асаф Шапира. 2008 г. Кратчайшие пути для всех пар с сублинейной аддитивной ошибкой. ICALP '08, Часть I, LNCS 5125, стр. 622–633, 2008.

Смотрите также

• Алгоритм Флойда-Уоршолла
• Тропическая геометрия