“Dijkstra bidireccional” por NetworkX

Acabo de leer la implementación de NetworkX del algoritmo de Dijkstra para las rutas más cortas utilizando la búsqueda bidireccional (en este caso ). ¿Cuál es el punto de terminación de este método?

Voy a basar esto en la implementación de networkx.

Dijkstra bidireccional se detiene cuando encuentra el mismo nodo en ambas direcciones, pero es posible que la ruta que retorna en ese punto no sea a través de ese nodo. Está haciendo cálculos adicionales para rastrear al mejor candidato para el camino más corto.

Voy a basar mi explicación en tu comentario (en esta respuesta )

Considere este gráfico simple (con los nodos A, B, C, D, E). Los bordes de este gráfico y sus pesos son: “A-> B: 1”, “A-> C: 6”, “A-> D: 4”, “A-> E: 10”, “D-> C: 3 “,” C-> E: 1 “. cuando uso el algoritmo de Dijkstra para este gráfico en ambos lados: en adelante, encuentra B después de A y luego D, al revés encuentra C después de E y luego D. en este punto, ambos conjuntos tienen el mismo vértice y una intersección. ¿Este es el punto de terminación o debe continuarse? porque esta respuesta (A-> D-> C-> E) es incorrecta.

Para referencia, aquí está el gráfico: introduzca la descripción de la imagen aquí

Cuando ejecuto el dijkstra bidireccional de networkx en la red (no dirigida) en el contraejemplo usted reclamó ese comentario: "A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1" : me da: (7, ['A', 'C', 'E']) , no ADCE .

El problema está en una mala interpretación de lo que está haciendo antes de que se detenga. Hace exactamente lo que está esperando en términos de búsqueda de nodos, pero mientras lo hace, se está produciendo un procesamiento adicional para encontrar la ruta más corta. Para cuando llega a D desde ambas direcciones, ya ha recostackdo algunas otras rutas “candidatas” que pueden ser más cortas. No hay garantía de que solo porque se llega al nodo D desde ambas direcciones que termina siendo parte del camino más corto. Más bien, en el punto en que se ha alcanzado un nodo desde ambas direcciones, la ruta más corta del candidato actual es más corta que cualquier ruta candidata que encontraría si continuara ejecutándose.

El algoritmo comienza con dos grupos vacíos, cada uno asociado con A o E

 {} {} 

y se construirán “grupos” alrededor de cada uno. Primero pone A en el cluster asociado con A

 {A:0} {} 

Ahora comprueba si A ya está en el grupo alrededor de E (que actualmente está vacío). No lo es. A continuación, mira a cada vecino de A y comprueba si están en el grupo alrededor de E Ellos no son. Luego coloca a todos esos vecinos en un montón (como una lista ordenada) de los vecinos próximos de A ordenados por longitud de ruta de A Llama a esto la ‘franja’ de A

 clusters ..... fringes {A:0} {} ..... A:[(B,1), (D,4), (C,6), (E,10)] E:[] 

Ahora comprueba E Para E hace lo simétrico. Coloque E en su grupo. Compruebe que E no está en el grupo alrededor de A Luego revise todos sus vecinos para ver si hay alguno en el grupo alrededor de A (no lo están). Entonces crea la franja de E

 clusters fringes {A:0} {E:0} ..... A:[(B,1), (D,4), (C,6), (E,10)] E:[(C,1), (A,10)] 

Ahora vuelve a A Toma B de la lista y lo agrega al clúster alrededor de A Verifica si algún vecino de B está en el grupo alrededor de E (no hay vecinos a considerar). Entonces tenemos:

 clusters fringes {A:0, B:1} {E:0} ..... A:[(D,4), (C,6), (E,10)] E:[(C,1), (A,10)] 

De vuelta a E : agregamos C al grupo de E y verificamos si algún vecino de C está en el grupo de A ¿Qué sabes, hay A . Por lo tanto, tenemos un candidato con el camino más corto ACE, con una distancia de 7. Lo mantendremos. Añadimos D para agregar a la franja de E (con distancia 4, ya que es 1 + 3). Tenemos:

 clusters fringes {A:0, B:1} {E:0, C:1} ..... A:[(D,4), (C,6), (E,10)] E:[(D,4), (A,10)] candidate path: ACE, length 7 

De vuelta a A : obtenemos lo siguiente de su franja, D Lo agregamos al grupo sobre A y notamos que su vecino C está en el grupo sobre E Así que tenemos una nueva ruta de candidato, ADCE , pero su longitud es mayor que 7, por lo que la descartamos.

 clusters fringes {A:0, B:1, D:4} {E:0, C:1} ..... A:[(C,6), (E,10)] E:[(D,4), (A,10)] candidate path: ACE, length 7 

Ahora volvemos a E Nos fijamos en D Está en el grupo alrededor de A Podemos estar seguros de que cualquier ruta candidata futura que encontremos tendrá una longitud al menos tan grande como la ruta ADCE que acabamos de trazar (esta afirmación no es necesariamente obvia, pero es la clave de este enfoque). Así que podemos detenernos. Devolvemos el camino candidato encontrado anteriormente.