Min-plus matrismultiplikation

Min-plus-matrismultiplikation , även känd som distansprodukt , är en operation på matriser .

Givet två $n\times n$ matriser $A=(a_{ij})$ och $B=(b_{ij })$ , deras avståndsprodukt $C=(c_{ij})=A\star B$ definieras som en $n\times n$ matris så att $c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{ kj}\}$ . Detta är standardmatrismultiplikation för halvringen av tropiska tal i min-konventionen.

Denna operation är nära relaterad till problemet med den kortaste vägen . Om $W$ är en $n\times n$ matris som innehåller kantvikterna för en graf , så ger $W^{k}$ avstånden mellan hörn med hjälp av längdbanor högst $k$ kanter, och $W^{n}$ är avståndsmatrisen för grafen.

Uri Zwick . 2002. Alla par kortaste vägar med hjälp av överbryggningsmängder och rektangulär matrismultiplikation . J. ACM 49, 3 (maj 2002), 289–317.
Liam Roditty och Asaf Shapira. 2008. Kortaste vägar i alla par med ett sublinjärt additivfel . ICALP '08, del I, LNCS 5125, s. 622–633, 2008.

Se även