En informática , las etiquetas de concentradores o el algoritmo de etiquetado de concentradores son una técnica de aceleración que consume muchos menos recursos que la tabla de búsqueda, pero sigue siendo extremadamente rápida para encontrar las rutas más cortas entre nodos en un gráfico , que puede representar, por ejemplo, redes de carreteras. [1]
Este método permite, como máximo, con dos sentencias SELECT y el análisis de dos cadenas, calcular el camino más corto entre dos vértices de un grafo. Para un grafo orientado como un grafo de carreteras, esta técnica requiere el cálculo previo de dos tablas a partir de estructuras construidas mediante el método de las jerarquías de contracción . Al final, estas dos tablas calculadas tendrán tantas filas como nodos presentes en el grafo. Para cada fila (cada nodo), se calculará una etiqueta.
Una etiqueta es una cadena que contiene la información de distancia entre el nodo actual (el nodo de la fila) y todos los demás nodos a los que se puede llegar con una búsqueda ascendente en la estructura multinivel relativa. La ventaja de estas distancias es que todas representan los caminos más cortos.
De esta forma, para futuras consultas, la búsqueda de la ruta más corta comenzará desde el origen en la primera tabla y el destino en la segunda tabla, desde donde buscará dentro de las etiquetas los nodos comunes con la información de distancia asociada. Solo la suma más pequeña de distancias se conservará como resultado de la ruta más corta.