oráculo de distancia

En computación , un oráculo de distancia (DO) es una estructura de datos para calcular distancias entre vértices en un gráfico .

Sea G ( V , E ) un grafo ponderado no dirigido, con n = | V | nodos y m = | mi | bordes Nos gustaría responder consultas del tipo "¿cuál es la distancia entre los nodos s y t ?".

Una forma de hacerlo es ejecutar el algoritmo de Dijkstra . Esto lleva tiempo y no requiere espacio adicional (además del propio gráfico). $O(m+n\log n)$

Para responder a muchas consultas de manera más eficiente, podemos dedicar algún tiempo a preprocesar el gráfico y crear una estructura de datos auxiliar.

Una estructura de datos simple que logra este objetivo es una matriz que especifica, para cada par de nodos, la distancia entre ellos. Esta estructura nos permite responder consultas en tiempo constante , pero requiere espacio extra. Se puede inicializar en el tiempo utilizando un algoritmo de rutas más cortas de todos los pares, como el algoritmo de Floyd-Warshall . ${\ estilo de visualización O (1)}$ ${\ estilo de visualización O (n ^ {2})}$ ${\ estilo de visualización O (n ^ {3})}$

Un DO se encuentra entre estos dos extremos. Utiliza menos espacio para responder consultas en menos tiempo. La mayoría de los DO tienen que comprometer la precisión, es decir, no devuelven la distancia exacta, sino una aproximación de la misma con un factor constante. ${\ estilo de visualización O (n ^ {2})}$ $O(m+n\log n)$