"Dijkstra bidirezionale" di NetworkX

Question

Ho appena letto l'implementazione NetworkX dell'algoritmo Dijkstra per i percorsi più brevi utilizzando la ricerca bidirezionale (a this). Qual è il punto di termine di questo metodo?

Answer 1

Ho intenzione di basare questo sull'implementazione di networkx.

Dijkstra bidirezionale si interrompe quando incontra lo stesso nodo in entrambe le direzioni, ma il percorso che restituisce in quel punto potrebbe non passare attraverso quel nodo. Sta facendo ulteriori calcoli per tracciare il miglior candidato per il percorso più breve.

ho intenzione di basare la mia spiegazione sul tuo commento (su this answer)

Considerate questo semplice grafico (con i nodi A, B, C, D, E). I bordi di questo grafico e il loro peso sono: "A-> B: 1", "A-> C: 6", "A-> D: 4", "A-> E: 10", "D-> C: 3" , "C-> E: 1". quando uso l'algoritmo Dijkstra per questo grafico su entrambi i lati: in avanti trova B dopo A e poi D, in indietro trova C dopo E e poi D. in questo punto, entrambi gli insiemi hanno lo stesso vertice e un'intersezione. Questo è il punto di terminazione o deve essere continuato? perché questa risposta (A-> D-> C-> E) non è corretta.

Per riferimento, ecco il grafico:

Quando eseguo Dijkstra bidirezionale di NetworkX sulla rete (non orientato) nel controesempio si sosteneva che commentare: "A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1": mi dà: (7, ['A', 'C', 'E']), non A-D-C-E.

Il problema è in un fraintendimento di ciò che sta facendo prima dello si ferma. Fa esattamente quello che ti aspetti in termini di ricerca dei nodi, ma, mentre sta facendo ciò, è in corso un'ulteriore elaborazione per trovare il percorso più breve. Quando raggiunge D da entrambe le direzioni, ha già raccolto alcuni altri percorsi "candidati" che potrebbero essere più brevi. Non vi è alcuna garanzia che solo perché il nodo D viene raggiunto da entrambe le direzioni che finisce per essere parte del percorso più breve. Piuttosto, nel momento in cui un nodo è stato raggiunto da entrambe le direzioni, il percorso più breve candidato corrente è più breve di qualsiasi percorso candidato che troverà se continuasse a funzionare.

L'algoritmo inizia con due gruppi vuoti, ciascuno associato con A o E

{}   {} 

e si accumula "cluster" intorno ciascuno. E prima mette A nel cluster associato con A

{A:0}   {} 

Ora controlla se A è già nel cluster attorno E (che al momento è vuoto). Non è. Successivamente, esamina ciascun vicino di A e controlla se si trova nel cluster intorno a E. Non sono. Mette poi tutti i vicini in un mucchio (come una lista ordinata) dei prossimi vicini di A ordinati per lunghezza del percorso da A. Chiamare questo la 'frangia' di A

clusters     .....  fringes 

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

Ora controlla E. Per E fa la cosa simmetrica. Inserire E nel relativo cluster. Verificare che E non si trovi nel cluster attorno a A.Quindi controlla tutti i suoi vicini per vedere se ce ne sono nel cluster intorno a A (non lo sono). Quindi crea la frangia di E.

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

Ora si risale al A. Prende B dall'elenco e lo aggiunge al cluster intorno a A. Controlla se il prossimo di B si trova nel cluster intorno a E (non ci sono vicini da considerare). Così abbiamo:

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

Torna E: aggiungiamo C tot egli gruppo di E e controllare se qualsiasi vicino di C è nel gruppo di A. Che cosa sai, c'è lo A. Quindi abbiamo un candidato percorso più breve A-C-E, con distanza 7. Ci atterremo a questo. Aggiungiamo D da aggiungere ai margini di E (con distanza 4, poiché è 1 + 3). Abbiamo:

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

candidate path: A-C-E, length 7 

Torna A: Otteniamo la prossima cosa dalla sua frangia, D. Lo aggiungiamo al cluster circa A e notiamo che il suo vicino C è nel cluster di circa E. Quindi abbiamo un nuovo percorso candidato, A-D-C-E, ma la sua lunghezza è maggiore di 7, quindi la scartiamo.

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

candidate path: A-C-E, length 7 

Ora torniamo a E. Guardiamo allo D. È nel cluster intorno a A. Possiamo essere certi che ogni futuro percorso candidato che incontreremo avrà lunghezza almeno pari al percorso A-D-C-E appena tracciato (questa affermazione non è necessariamente ovvia, ma è la chiave di questo approccio). Quindi possiamo fermarci. Restituiamo il percorso candidato trovato in precedenza.