Multiplicación de matrices min-plus

La multiplicación de matrices min-plus , también conocida como producto de distancia , es una operación sobre matrices .

Dados dos${\displaystyle n\times n}$matrices${\displaystyle A=(a_{ij})}$y${\displaystyle B=(b_{ij})}$, su producto de distancia${\displaystyle C=(c_{ij})=A\star B}$se define como un${\displaystyle n\times n}$matriz tal que${\displaystyle c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}}$. Esta es la multiplicación de matrices estándar para el semianillo de números tropicales en la convención min.

Esta operación está estrechamente relacionada con el problema del camino más corto . Si${\displaystyle W}$es un${\displaystyle n\times n}$matriz que contiene los pesos de las aristas de un grafo , entonces${\displaystyle W^{k}}$da las distancias entre vértices usando caminos de longitud como máximo${\displaystyle k}$bordes y${\displaystyle W^{n}}$es la matriz de distancias del grafo.

• Uri Zwick . 2002. Caminos más cortos entre todos los pares utilizando conjuntos puente y multiplicación de matrices rectangulares . J. ACM 49, 3 (mayo de 2002), 289–317.
• Liam Roditty y Asaf Shapira. 2008. Rutas más cortas entre todos los pares de nodos con un error aditivo sublineal . ICALP '08, Parte I, LNCS 5125, págs.  622–633, 2008.

• Algoritmo de Floyd-Warshall : un algoritmo en teoría de grafos. 
• Geometría tropical : versión esqueletizada de la geometría algebraica.