di interpretazione Dijkstra Algoritmo

Question

capisco come trovare il percorso più breve dall'inizio alla fine come ha spiegato l'algoritmo di Dijkstra, quello che non capisco è l'interpretazione. Qui, dal grafico nella figura, l'ordine aggiunto al mio set noto da A ad E è A,C,B,D,F,H,G,E quello che non ottengo è, come ottenere il percorso da A ad E come mostrato nell'immagine (l'aspetto matematico)

Answer 1

Ogni nodo ha un nodo genitore. Quando raggiungi lo 'E', devi semplicemente controllare il suo genitore e così via fino a trovare 'A'. In questo modo troverai la lista in ordine inverso. Invertire l'elenco per trovare il percorso da 'A' a 'E'.

L'elenco dei genitori sarà 'E' 'G' 'H' 'F' 'B' 'A' se si aggiunge in ordine.

NOTA: Il "nodo padre" è il nodo indicato nella colonna "percorso" della tabella

Answer 2

consideri una coda di priorità minima contenente percorsi da attraversare in cui la priorità del percorso sulla coda è il costo di attraversare i bordi nel percorso dalla radice fino al bordo incluso. Ad ogni passo dell'algoritmo pop il percorso più basso costo dalla coda e, considerando ciascuno dei suoi bordi incidenti, estendere il percorso con quel bordo incidente e spingere il nuovo percorso di nuovo in coda in ordine di priorità. Ripeti fino a quando il primo percorso raggiunge la destinazione.

Ad esempio:

1. Start con una coda vuota <>
2. Poi, a partire dalla radice A, mettere tutti gli archi incidenti (A->B, A->C e A->D con costi 2, 1 e 4 rispettivamente) in coda e ordinare per priorità: <(A->C,1),(A->B,2),(A->D,4)>
3. Inserire il percorso di priorità minima A->C dalla parte anteriore della coda e quindi considerare i bordi incidenti alla fine del percorso C e spingere quei sentieri indietro sulla coda (mantenere l'ordine di priorità): <(A->B,2),(A->D,4),(A->C->A,10),(A->C->E,12)>
4. Ripetere, popping il percorso della priorità minima A->B fuori ed estendendo i percorsi con i bordi incidenti: <(A->D,4),(A->B->F,4),(A->B->C,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
5. Continuate ... pop e spingere A->D più bordi incidenti: <(A->B->F,4),(A->D->C,6),(A->B->C,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
6. pop A->B->F e spingere più bordi incidenti: <(A->D->C,6),(A->B->C,7),(A->B->F->H,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
7. pop A->D->C - tuttavia, abbiamo già raggiunto C con un percorso di costo inferiore in modo da può ignorarlo.
8. pop A->B->C e ignorarlo.
9. pop A->B->F->H e spingere più bordi incidenti: <(A->B->F->H->G,8),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
10. pop A->B->F->H e spingere più bordi incidenti: <(A->B->F->H->G->F,10),(A->C->A,10),(A->B->F->H->G->E,11),(A->B->E,12),(A->C->E,12)>
11. pop A->B->F->H->G->F e ignorarlo.
12. pop A->C->A e ignorarlo.
13. pop A->B->F->H->G->E e abbiamo raggiunto l'obiettivo (con un costo di 11)!

Answer 3

A partire dal nodo di inizio, viene eseguito un calcolo del peso cumulativo quando si attraversa il grafico verso i nodi disponibili. Il peso cumulativo da un nodo a un nodo adiacente viene confrontato con qualsiasi risultato precedente (cioè, possibili attraversamenti su quel nodo). Il percorso con il peso cumulativo più basso viene quindi selezionato come "vincitore". Il processo si ripete fino a quando non viene trovato un percorso dal nodo iniziale a quello terminale e valutato come il peso cumulativo più basso.

Quindi, nell'esempio vi hanno dimostrato:

• ACE = 12
• ADCE = 17
• ABE = 12

ABFHGE è l'unico percorso di sinistra (nel grafo orientato) con il peso cumulativo più basso di 11 (e anche il percorso più lungo) dall'inizio alla fine.

Come si calcola dall'inizio, alcuni percorsi possono sembrare inizialmente più corti (AC), ma man mano che l'algoritmo progredisce queste scelte vengono abbandonate quando vengono esplorati tutti i percorsi da A a E.