Min-plus maticové násobení

Min-plus násobení matic, známé také jako vzdálenostní součin, je maticová operace.

Jsou-li dány dvě matice $n\times n$, $A=(a_{ij})$ a $B=(b_{ij})$, jejich vzdálenostní součin $C=(c_{ij})=A\star B$ je definován jako matice $n\times n$ taková, že $c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}$. To je standardní násobení matic v polookruhu tropické geometrie pro min konvenci.

Tato operace má těsnou souvislost s problémem nejkratší cesty. Pokud $W$ je matice $n\times n$ obsahující délky hran grafu, pak $W^{k}$ udává vzdálenosti mezi vrcholy při použití cest obsahujících nejvýše $k$ hran, a $W^{n}$ je matice vzdáleností grafu.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Min-plus matrix multiplication na anglické Wikipedii.

• ZWICK, Uri, 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of ACM. Roč. 49, čís. 3 (květen 2002), s. 289–317. Dostupné online. 
• RODITTY, Liam; SHAPIRA, Asaf, 2008. All-Pairs Shortest Paths with a Sublinear Additive Error. In: ICALP '08, Part I, LNCS 5125. [s.l.]: [s.n.]. Dostupné online. S. 622–633.

Související články

• Floydův–Warshallův algoritmus
• Tropická geometrie