Bi Directional Dijkstra
1.0.0
Dado un gráfico con pesos de borde no negativos, un vértice de origen y un objetivo Vertec t . Encuentra el camino más corto entre S y T
Pero, ¿por qué no usamos el algoritmo de Dijkstra para resolver el problema?
0 (e + vlogv) es la peor complejidad del tiempo del algoritmo de Dijkstra, que es bastante rápido. Pero, para un gráfico con 20 millones de vértices y 50 millones de bordes, funcionará durante varios segundos en promedio. Entonces, necesitamos algo significativamente más rápido.
Antes de entrar en los detalles de la búsqueda bidireccional, exploremos el concepto de "seis grados de separación"
- En 1929, un autor húngaro, Fragyes Karinthy, propuso por primera vez el concepto de "seis grados de separación" en sus historias cortas.
- Seis grados de separación es la idea de que todos los seres vivos y todo lo demás en el mundo están a seis o menos pasos de distancia el uno del otro.
Ahora, veamos la red social más popular, Facebook. Supongamos que una persona promedio en Facebook tiene alrededor de 100 amigos. Entonces, si consideramos amigos de amigos de esa persona, serán 100*100 los que son 10,000 amigos de amigos. Si consideramos "amigos de amigos de amigos" , eso será 100 veces más o 1 millón. Y si continuamos eso seis veces, tendremos 1 billón de personas.
Pero, la población global es de 7,6 mil millones.
Ahora, ¿cómo encontramos la ruta más corta entre dos personas al azar A y B a través de sus conexiones en la red social?
Consideremos la búsqueda bidireccional. Por lo tanto, consideraremos amigos de amigos de amigos de A y Friends of Friends of B.
Tenga en cuenta que tendremos aproximadamente 1 millón de amigos de amigos de amigos para A y B. Por lo tanto, en total consideraremos solo 2 millones de personas en este caso.
El algoritmo normal de Dijkstra tendría que mirar a aproximadamente 2 mil millones de personas en la red social para encontrar el camino más corto entre A y B.
En esto, realizamos dos búsquedas simultáneas: una delantera desde el estado inicial, y una hacia atrás desde la meta, deteniéndose cuando los dos se encuentran en el medio.
- Construir gr (gráfico invertido)
- Iniciar dijstra desde s (fuente) en g y desde t (objetivo) en GR
- Alternar entre los pasos de Dijkstra en G y en GR
- Detente cuando se procese un vértice "V" tanto en G como en GR.
- Calcule el camino más corto entre S y T.
Cálculo de la ruta más corta entre S y T: Deja que Dist [u] sea la estimación de distancia en el dijkstra delantero de S en G. Deja que Distr [u] sea la estimación de distancia en el dijkstra hacia atrás de t en gr. Después de que se procesa un nodo "V" tanto en G como en GR, alguna ruta más corta de S a T pasa a través de algún nodo "U" que se procesa en G, en GR o Ambos y D (S, T) = Dist [U] + Distr [U]
