Ben tornato.
Ora che abbiamo il grafico ponderato, possiamo passare alla dieta.
Bello.
No.
Eccoci.
È uno scherzo stupido, ma in realtà i tre tentativi mi hanno portato a farlo bene.
Mi dispiace rovinare la sua eredità.
Non riesco mai a ricordare come si scrive il suo nome ma è quello in basso qui.
D i j.
In ogni caso, ciò che faremo ora è di descrivere i passaggi di come l'algoritmo funziona per voi per
visualizzarlo visivamente un passo alla volta prima di tradurlo in codice.
E il grafico con cui lavoreremo è di questo tipo.
Quindi è un grafico ponderato.
Qui puoi sapere a cosa sono associati sei vertici e ogni spigolo.
Speriamo sia chiaro che cosa va con ciò che e il percorso il percorso più breve che vogliamo trovare
è dalla A alla Z.
Quindi ci sono un paio di opzioni.
Questo è un grafico molto piccolo e la maggior parte di quelli nel mondo reale sono piuttosto grandi.
Ma anche con questo piccolo set di dati ci sono molti modi per ottenere da A a.
È possibile aggirare i bordi che si possono attraversare nel mezzo, ecco le quattro opzioni più.
Per non parlare, potrebbe prendere alcuni involucri assurdi per arrivare lì compresi i loop in ogni caso.
Questo è il nostro obiettivo.
Quindi ecco l'algoritmo.
Bollito o distillato in quattro passaggi principali ogni volta attraverso il ciclo principale farà qualcosa di simile.
Quindi cerchiamo di visitare un nuovo nodo che tu sappia che l'unico modo in cui funziona è stato riavviato a e visitiamo
i nodi e ci deve essere un ordine in cui li visitiamo.
Come decidiamo dove andare avanti e iniziamo selezionando il nodo con la minima distanza nota da
visitare per primo.
Quindi tornerò a tutto ciò visivamente in un attimo.
Ma prendiamo sempre il nodo che ha la minima distanza nota da A.
E lo visitiamo prima, poi, una volta che ci spostiamo su quel nodo, guardiamo ognuno dei suoi vicini
e poi per ciascuno dei suoi vicini sommiamo la distanza da A a quel vicino.
E se è più piccolo di quello che sappiamo attualmente se è una distanza minore, aggiorniamo il nostro
file.
Essenzialmente questo è molto di cui parlare senza mostrarti.
Quindi ho un mucchio di diagrammi come questo.
Ci arriveremo tra un attimo ma quelli sono i passaggi.
Quindi ogni volta che visitiamo un nuovo nodo ogni volta che cerchiamo di iniziare il ciclo, visitiamo la
distanza più piccola conosciuta da A.
Nel nostro caso ne stiamo cercando otto.
Quindi iniziamo con quello che ci spostiamo su quel nodo e guardiamo ognuno dei suoi vicini e per
ogni vicino abbiamo già una distanza sul file quanto dista da a.
E lo aggiorneremo se la nuova distanza che abbiamo insieme è inferiore a quella che conosciamo
attualmente.
E so che sembra pazzesco.
Quindi tornerò su di esso.
Ma ecco il nostro diagramma.
Questa è una specie di setup per i prossimi 30 qualcosa, forse 40 diapositive, e svanisce tra loro e vedrai cose
che vanno e vengono.
Quindi lo stesso grafico è qui sopra.
Stiamo andando da A a E.
Ha gli stessi valori lì.
E qui sotto c'è una specie di file a cui mi riferivo dove conserviamo la distanza più breve
da a per ogni vertice.
Quindi A è un caso speciale perché sarà zero ma qualcosa come B Bene alla fine la distanza più breve
da A a B è quattro.
Ovviamente.
Ma poi come E a cui arriveremo, il nostro obiettivo è capire quale sia la distanza più breve.
E comunque aggiorneremo questo mentre andiamo.
E poi precedente.
Spiegherò tra poco.
Quindi iniziamo e la prima cosa che facciamo è inizializzare le distanze più brevi da a per
ogni vertice.
E non sappiamo davvero come farlo.
Questo è il punto.
Non sappiamo quale sia la distanza più breve da a per arrivare a F ..
Immagina ci siano un milione di vertici qui.
Non puoi solo sapere dall'inizio.
Quindi cosa facciamo.
Abbiamo appena messo l'infinito qui, mettiamo un grande valore fondamentalmente uno sconosciuto.
Non possiamo non conoscere nessuno di questi valori tranne uno che sappiamo che la distanza più breve da A
ad A è zero da un vertice a se stesso.
Sarà zero.
Questo è ciò che iniziamo con questo è come inizializziamo sempre il set up.
Quindi creeremo una struttura dati per questo, non parleremo ancora di codice.
Ma immagina di scriverlo su un pezzo di carta.
Quindi da A ad A è zero da A a B.
In questo momento è l'infinito che non conosciamo.
Dalla A alla Z è l'infinito.
Quindi lo ignoriamo.
Ora ricorda i passaggi.
La prossima cosa che facciamo ogni volta che cerchiamo di visitare un nuovo nodo.
Dovremmo scegliere il nodo con la distanza più piccola conosciuta da visitare per primo.
Bene, abbiamo una scelta in questo momento.
Questo è il più piccolo.
0 è chiaramente più piccolo dell'infinito.
Quindi iniziamo con A.
Quindi prendiamo il più piccolo.
Questo è quello che mostra qui.
E l'ho aggiunto all'elenco visitato qui.
Ora quello che dobbiamo fare è guardare ognuno dei suoi vicini.
Quindi da un abbiamo due scelte da A a B A da vedere e io vado sempre in ordine alfabetico.
Non importa
Quindi inizieremo da A a B.
Quindi, quello che facciamo è scendere a B e controlliamo.
Bene, attualmente la distanza più breve da A a B è infinita perché non ne sappiamo di migliori.
Questo è solo lo stato iniziale, quindi quello che abbiamo scoperto è che la distanza da A a B qui è quattro.
Quindi quattro è decisamente inferiore all'infinito.
Quindi aggiorniamo questo per dire che la nuova distanza più breve da A è 4 e vedremo che aggiorneremo alcuni di
questi un paio di volte.
Ovviamente possiamo vedere guardando il grafico.
Non c'è niente di più breve tra A e B sono decisamente quattro.
Questo è il più piccolo che otterremo.
OK.
Quindi aggiorniamo che qui e poi qui in questa struttura precedente che stiamo per aggiornare si dice che sia
uguale a A.
Quindi quello che essenzialmente fa e so che mi mancano le virgolette non è un codice valido, ma quello che
fa è che il modo in cui siamo arrivati è stato attraverso un.
E questo è ovvio in questa situazione.
Ma in seguito qualcosa come f se aggiorniamo la distanza più breve da f vogliamo ricordare che ci arriviamo
da D.
O siamo arrivati da C ..
Ci sono più opzioni.
Quindi questa struttura ci aiuta a ricostruire il punto in cui siamo venuti dal nodo che è successo o quello che
è successo prima di essere sul nostro cammino.
Quindi questo è semplice.
Quindi abbiamo fatto tutto ciò che dovevamo fare per a-b.
Ora guardiamo a per vedere.
OK.
Quindi attualmente dalla a alla c abbiamo l'infinito.
Quindi guardiamo a quella distanza il totale è due.
Quindi ovviamente aggiorneremo anche questo è decisamente più breve.
E poi veniamo qui per vedere e invece di No lo aggiorniamo per dire che il modo in
cui abbiamo avuto modo di vedere è stato da un e per un abbiamo fatto entrambi i vicini per nota.
Quindi ora quello che ci resta da fare è ripetere il processo.
Prendiamo il valore più piccolo conosciuto dalla distanza più breve da A.
Che non abbiamo visitato
Quindi ricorda che siamo stati a.
Quindi non ne sceglieremo una perché continuiamo a fare continuamente e ancora e ancora e ancora.
Ma ora abbiamo due scelte.
B La distanza è 4 e C la distanza è due.
E quando dico distanza è la distanza dal nodo.
OK.
Quindi, come puoi vedere, iniziamo con C che è la distanza più piccola conosciuta.
Quindi ora guardiamo a c e ai suoi vicini e ci sono tre scelte ma abbiamo già fatto otto C
quindi non lo faremo.
Quindi ora abbiamo C a D e C a F.
Tutto ok.
Diamo prima un'occhiata a c a d.
Quindi, quello che facciamo di nuovo è guardare quale sia il valore corrente da A a D.
È memorizzato all'infinito.
Quindi calcoliamo il nuovo valore da A a D a C e il modo in cui lo facciamo è sommando da A a C più
C a D.
Quindi, ad esempio, sappiamo che C-D è di due tipi, quindi prendine due e poi guardiamo come abbiamo visto cosa era
il precedente per C e il precedente è a.
Quindi quindi capiamo qual è la distanza da A a C 2.
Quindi due più due ci danno quattro, naturalmente.
E ovviamente è facile da guardare, ma devi pensare a cosa farà il
tuo codice.
Quindi sommiamo quei due insieme.
Ne danno solo quattro.
E aggiorneremo questo qui per risparmiare.
Questo è decisamente più piccolo dell'infinito.
E poi dobbiamo anche aggiornare qui per dire come siamo arrivati a D e il modo in cui siamo arrivati è stato attraverso
C ..
Quindi questo è ciò che aggiungiamo.
OK.
Il prossimo andremo a guardare da C a F.
Stesso processo
Quindi da C a F è 4 e quindi da A a C è 2.
E il modo in cui sappiamo che è sicuramente questo vantaggio è se guardiamo c abbiamo memorizzato come il precedente Il modo più
breve per arrivarci.
Quindi due più quattro ci danno sei.
Quindi arriviamo a F e controlliamo sei meno dell'infinito.
Sì.
Quindi lo aggiorniamo.
Quindi ne memorizziamo sei qui e quindi quello che dobbiamo fare è aggiornare il nostro precedente.
Come siamo arrivati a f ..
Bene, cosa è successo prima che fosse C, quindi spero che tu possa vedere come questo diventa utile.
Quello che stiamo memorizzando qui è il percorso più breve per ogni dato nodo da a.
Quindi il modo più breve per arrivare a D è da C e quindi il modo più breve per arrivare a vedere da un
è direttamente da.
Quindi abbiamo solo bisogno di memorizzare il percorso più breve precedente.
Quindi è una sorta di passo dopo passo come arriviamo a ciascun nodo Qual è il modo più breve per arrivarci.
E li abbiamo combinati tutti per capire come arrivare ad e, infine, che non è stato fatto.
Quindi lo aggiorniamo per dire che siamo venuti da C ..
Ora ricominciamo.
Dobbiamo scegliere il valore più piccolo tra la distanza più breve da A che non abbiamo visitato.
Quindi abbiamo fatto a e c in modo da poterli eliminare e la cosa più breve è b con 4 d con 4 o F
con sei.
Beh, sicuramente non sei e sto scegliendo B First solo perché viene prima in ordine alfabetico.
Ma nessuno dei due avrebbe funzionato.
Sono entrambi quattro.
Quindi ora guardiamo a B e B è facile perché abbiamo già visitato A a B.
Quindi non sta succedendo.
Ma abbiamo B da mangiare.
OK.
Quindi vedremo quello.
E questo ci dà tre più ciò che è venuto prima che B arrivasse a B da cui provenivamo.
Quindi quel limite è quattro.
Quindi tre più quattro ci danno sette come nuovo totale.
E questo è decisamente meno dell'infinito.
Quindi aggiorniamo questo per dire che l'attuale modo più breve che possiamo ottenere per Z è di 7 unità o qualunque sia questo
sette miglia o qualcosa del genere.
E poi il modo in cui siamo arrivati qui aggiorneremo questo per dire che siamo venuti da B.
Destra.
Quindi se ci fermassimo adesso non è la strada più breve ma abbiamo un percorso che potremmo mettere insieme.
Quindi siamo arrivati da e da B e siamo arrivati da a.
Ora fuori dai nodi non visitati dove andiamo.
Quindi abbiamo fatto un b c e ora abbiamo DNF o che è il più piccolo D.
Quindi andiamo al prossimo.
OK.
Quindi ecco D.
E abbiamo un paio di opzioni.
Siamo già stati a vedere.
Quindi non stiamo andando in quel modo.
Quindi andiamo a mangiare o F sto andando in ordine alfabetico, quindi viene prima.
Quindi vedremo d e.
Quindi quel limite è tre.
Quindi ora calcoliamo la distanza totale da A a E attraverso D.
Quindi il totale qui è 7.
E se guardiamo a ciò che abbiamo archiviato per adesso, è già alle 7.
In modo che non vince.
Non è meno.
Non è più breve
Quindi non lo aggiorneremo.
Potresti, se lo volessi, scrivere il tuo codice che hai aggiunto sette qui se sono uguali.
Ma non c'è ragione per cui abbiamo già un percorso lungo 7 unità.
Questo.
Quindi lo ignoriamo.
Ora passiamo al successivo che è D a F.
Quindi il nostro nuovo totale qui arriva a F è 5 e se guardi ciò che abbiamo immagazzinato in questo momento ne abbiamo sei.
Ben cinque sono meno di sei.
Quindi lo aggiorniamo per dire cinque e veniamo qui e non veniamo più da C. Questo è quello che avevamo
prima.
Questo era il modo più breve per arrivare a F ..
Ma ora è più breve se veniamo da D.
Quindi lo aggiorniamo.
Quindi questo sta dicendo che tu sai che il modo più veloce per arrivare a F è da D.
Il più vicino il percorso più breve da A a D è attraverso C la via più breve da A a C è buona perché c'è una
linea diretta dalla A alla Z.
OK.
Quindi finisce D.
Abbiamo fatto questo vantaggio, abbiamo fatto questo vantaggio.
Quindi ora lo cancelliamo.
Abbiamo visitato.
Eccoci.
Ora andremo a scegliere il più piccolo di nuovo.
Quindi abbiamo due opzioni.
Abbiamo visitato tutti questi per un b c e d.
Ora abbiamo E e F che è la più piccola che ha la distanza più vicina o il percorso più breve per a.
Adesso che è f 5 è più piccolo di 7.
Quindi inizieremo qui e abbiamo solo un'opzione.
Abbiamo già fatto questo vantaggio, abbiamo fatto questo vantaggio.
Quindi ora guardiamo a f t.
Quindi la distanza è una da percorrere da sinistra a E.
E qual è il percorso più breve per arrivare a f ..
Quindi aggiungiamo che tutti insieme 4 5 6.
E se guardiamo a ciò che attualmente abbiamo memorizzato per e abbiamo 7 abbiamo 7 da questo percorso all'esterno.
Ora abbiamo trovato qualcosa di più breve.
Quindi aggiorniamo questo per eliminarli.
E ora ne aggiungiamo sei.
E poi, naturalmente, dobbiamo aggiornare il modo in cui siamo arrivati perché adesso stiamo memorizzando la vecchia versione se
la guardi.
Stavamo dicendo che il percorso più breve dalla A alla Z passa per B, ma non è questo il caso.
Ora abbiamo appena trovato qualcosa di più breve dove passiamo attraverso F.
Quindi aggiorniamo questo.
Se guardiamo a E.
Eccoci.
Ora diciamo che il modo più breve per arrivarci è attraverso F e solo che la differenza di una
lettera ora fa un'enorme differenza perché è una cascata è una catena perché guardiamo dove F ..
Va bene, solo per arrivare a F, abbiamo attraversato D per arrivare a DeviantArt C per vedere che abbiamo attraversato.
E a questo punto non abbiamo più dove andare.
Oltre a E.
E questo significa che in realtà abbiamo finito.
Abbiamo trovato il percorso più breve.
Quindi, per abbatterlo di nuovo, non andrò avanti passo dopo passo, ma ogni volta scegliamo l'attuale distanza più piccola
da quella che non abbiamo visitato.
Esploriamo ciascuno dei suoi vicini e Koukl è la nuova distanza più breve per ogni vicino e se è più
piccola di quella che abbiamo già archiviato, aggiorniamo ciò che abbiamo archiviato e poi riflettiamo il cambiamento qui
nella nostra precedente struttura dati.
E questo ci permette di mettere insieme tutto.
Quindi se guardiamo a ciò che abbiamo finito ora tutto ciò che dobbiamo fare è lavorare all'indietro.
Quindi per andare da e abbiamo iniziato e lo guardiamo.
Tutto ok.
Bene, per arrivare a F da un modo il più breve possibile è tutto ciò che immagazziniamo finiamo con
un elenco del modo più breve per arrivare a qualsiasi nodo dal modo più breve per arrivare a D da a è attraverso C e arrivare al
C dobbiamo andare da a.
Quindi una C D.
Questo è il modo più breve per arrivarci.
Il modo più breve per arrivare è attraverso F e da f prima vai attraverso D da D.
Attraversiamo la C.
Quindi questo è il nostro percorso più breve.
A C D F D.
Quindi l'algoritmo di Dexters funziona non solo se per darti il percorso più breve tra due nodi alla fine il modo
in cui lo implementiamo avrà una struttura dati che ci darà il percorso più breve da A a tutti
i nodi e che può essere molto utile.
Se sai che lo fai una volta e non cambi il grafico.
Hai questa struttura che ti dà il percorso più breve per andare ovunque.
Non è necessario eseguirlo nuovamente per tutti quelli che si conoscono se si sta tentando di passare da A a B
e quindi da a a ed e si esegue contemporaneamente e si ottengono tutte queste informazioni.
Tutto ok.
Quindi so che è molto.
Ho fatto queste diapositive impiegate per sempre e spero che fossero utili.
Consiglio vivamente di superarli per conto proprio e senza di me, in qualche modo, spiegando cosa sto facendo
nel video che sta provando o anche su un pezzo di carta.
È così che l'ho imparato in origine.
Letteralmente carta da grafico che disegna questi grafici e ti tiene traccia di ciò che sai.
Tutto ok.
Siamo stati a un cross-off ci pieghiamo per essere cancellati e disegnare il grafico perché da qui il salto verso il
codice non è poi così male.
Sarà difficile se non sei sicuro di come funzioni effettivamente.
Quindi ti consiglio davvero di farlo se sei affatto confuso.
Se non ti va di guardare il video, non gioco a lungo senza audio.
Non è così eccitante da affrontare, ma può essere un po 'più coinvolgente se lo fai da solo.
E poi, una volta capito, saltare al codice è molto più semplice.
Tutto ok.
Quindi è quello che faremo dopo.
In realtà ti mostrerò una specie di vero pseudo-codice, se vuoi.
E poi se vuoi puoi provare e implementarlo o perché è un po 'complicato.
Totalmente comprensibile se solo codice insieme a me.
Tutto ok.
Questo succederà dopo.