Calcular distancias de camino más corto es un primitivo fundamental en el contexto de la minería de datos de grafos, ya que este tipo de información es esencial en una amplia gama de aplicaciones prominentes, que incluyen análisis de redes sociales, enrutamiento de datos, optimización de búsqueda web, diseño de bases de datos y planificación de rutas. Los algoritmos estándar para caminos más cortos (por ejemplo, Dijkstra) no escalan bien con el tamaño del grafo, ya que tardan más de un segundo o tienen grandes costos de memoria para responder una sola consulta en conjuntos de datos de grafos a gran escala. Por lo tanto, no son adecuados para extraer distancias de grafos grandes, que se están convirtiendo en la norma en la mayoría de los contextos de aplicaciones modernas. Por lo tanto, para lograr respuestas de consulta más rápidas, se han diseñado métodos más inteligentes y escalables, siendo los más efectivos de ellos los basados en precomputar y consultar una representación compacta del cierre transitivo del grafo de entrada, llamado etiquetado 2--. Para utilizar tales enfoques en escenarios realistas, cuando el grafo administrado experimenta modificaciones topológicas con el tiempo, se han introducido métodos específicos para actualizar cuidadosamente el etiquetado a medida que el grafo evoluciona. De hecho, recalcular desde cero la estructura 2-- cada vez que cambia el grafo no es una opción, ya que induce costos de tiempo insostenibles. Si bien el algoritmo dinámico de vanguardia para actualizar un etiquetado 2-- contra modificaciones (inserciones de arcos/vértices, disminuciones de pesos de arcos) ofrece tiempos de actualización muy rápidos, la única solución conocida para modificaciones (eliminaciones de arcos/vértices, aumentos de pesos de arcos) aún está lejos de considerarse práctica, ya que requiere hasta decenas de segundos de procesamiento por actualización en varias clases prominentes de entradas del mundo real, como lo muestra la experimentación. En este documento, presentamos un nuevo algoritmo dinámico para actualizar etiquetados 2-- contra cambios decrementales. Probamos su corrección, analizamos formalmente su rendimiento en el peor de los casos y evaluamos su efectividad a través de una evaluación experimental que emplea tanto entradas del mundo real como sintéticas. Nuestros resultados muestran que mejora, hasta en varias órdenes de magnitud, los tiempos de actualización promedio del único algoritmo decremental existente, representando así un paso adelante hacia la minería de distancias en tiempo real en general, en grafos masivos en evolución temporal.