La multiplicación de matrices mínima más , también conocida como producto de distancia , es una operación sobre matrices .
Dado dos matrices y , su producto a distancia se define como un matriz tal que . Esta es la multiplicación de matrices estándar para el semianillo de números tropicales en la convención mínima.
Esta operación está estrechamente relacionada con el problema del camino más corto . Si es un matriz que contiene los pesos de los bordes de un gráfico , luego da las distancias entre vértices utilizando trayectorias de longitud como máximo bordes, y es la matriz de distancias del gráfico.
Referencias
- Uri Zwick . 2002. Todos los pares de caminos más cortos utilizando conjuntos de puentes 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 de todos los pares con un error aditivo sublineal . ICALP '08, Parte I, LNCS 5125, págs. 622–633, 2008.