Așa că acum avem prioritatea de bază.
Am vorbit despre cum funcționează.
Iată și Sudoku-ul.
In regula.
Deci, definiți funcția pe grafic și definiți-o ca o metodă pe clasa grafului ponderat ponderat.
Doar numiți calea cea mai scurtă sau Dykstra sau orice altceva pentru tine.
Ar trebui să accepte un vertex de pornire și un vârf care se termină de la 8 la A la Z.
Mergem de la SFO la L. A. X. indiferent de numele vertexelor.
Se acceptă să înceapă și să se încheie ceea ce survine mai întâi va începe în cazul nostru, atunci avem nevoie
să realizăm câteva structuri de date și vom crea obiectul pe care îl putem numi distanțe.
Acesta va acționa ca acest tabel aici, unde pentru fiecare vârf vom stoca distanța cea mai scurtă curentă de
la orice punct de pornire.
Nu trebuie să fie bine, dar să spunem că lucrăm din nou cu un a.
Vom păstra în acest obiect cea mai mică distanță de la A la B de la A la C la D și de
la început vom inițializa totul până la infinit.
Dacă vă amintiți acest lucru pentru că nu știm cât de departe este de la A la C sau ADA D Singura valoare pe
care o știm cu siguranță este o zi pe care o pornim de la zero.
Apoi, după inițializarea valorilor și a obiectului distanțe, vom face, de asemenea, coada noastră prioritară.
Deci, facem o coadă de priorități noi și începe să fie goală și adăugăm fiecare dintre nodurile noastre în coada
de priorități unde am stabilit prioritatea ca fiind distanța de la A.
Deci, în principiu, adăugăm toate nodurile cu prioritatea infinitului, cu excepția unei priorități de
zero.
Așa că, bineînțeles, primim o primă, dar mai târziu vom avea valori actuale care nu sunt infinit.
Și de fiecare dată când scapăm, obținem cea mai mică valoare înapoi și de aici începem.
Asta vom vizita mai întâi.
O.K.
Deci, acest lucru inițializează lucrurile.
Și mai este un pas.
De asemenea, trebuie să creăm obiectul anterior, unde este doar un obiect simplu în care avem o cheie
pentru fiecare vertex și îl inițializăm la o valoare de nu.
Deci asta e structura de date aici.
Dar totul ar trebui să înceapă la nr.
Și vom actualiza valoarea pentru fiecare cheie în timp ce mergem.
In regula.
Deci este în principal setul care necesită ceva timp pentru a explica.
Apoi, doar buclele, atâta timp cât există ceva în coada de priorități.
Atâta timp cât este ceva de vizitat, vom elimina vârful în coada de priorități.
Asta inseamna ca alegem cea mai mica distanta de la ceea ce vom incepe cu sa spunem D pentru ca are o
valoare de 2 si orice altceva are o valoare de 4 sau 6 sau 10 sau ceva.
Deci, începem cu asta și apoi primul lucru pe care îl facem este să verificăm.
Este acest vârf pe care încerc să-l fac să fi lovit sfârșitul și dacă acesta este cazul, atunci am terminat.
În caz contrar, vom trece prin fiecare dintre vecinii săi, astfel încât să ne uităm la
toți vecinii pentru D și vom calcula distanța până la acel vârf de la începutul vertexului și apoi dacă noua distanță care sumă
este mai mică decât ceea ce stocăm în prezent actualizăm distanțele obiect cu o nouă distanță mai mică.
Deci, asta este tot ce am făcut în ultimul videoclip sau în două videoclipuri pe care le mergem.
Actualizăm distanța pe care o actualizăm obiectul anterior pentru a reflecta acum de unde am venit.
Apoi, atunci vom vedea același vârf cu o nouă distanță totală față de nota de început și asta este.
Continuăm mereu.
De exemplu, aici vom alege cea mai mică valoare utilizând coada de priorități.
În prezent ar avea D E și F acolo pentru că am făcut o C și B.
Așadar, am dequeue care ne-ar da D pentru că este cel mai mic, cu o valoare de patru.
Deci, atunci ne vom uita la acești vecini.
Există două CNF și începem să ne uităm la summit, împreună ne dă 7 care nu este de fapt mai puțin decât ceea ce
avem în prezent.
Deci nu facem nimic.
Dar apoi mergem spre următorul vecin al lui D.
Așa că ne dă cinci.
Și dacă te uiți la ceea ce am păstrat acum este de 6 ani.
Deci 5 Noul total este cu siguranță mai mic de 6.
Deci, îl actualizăm aici.
Apoi, am ajuns la precedent și ne spunem că noua cale mai scurtă de a ajunge la F nu este de la C, de
fapt, este de fapt să treacă prin D.
Așa că am pus doar D acolo și apoi, după care vrem să terminăm Q f cu noua valoare de 5, astfel încât să fie actualizată
în coada noastră prioritară și știm că data viitoare vor alege mai întâi 5, pentru că este noua
valoare cea mai mică.
In regula.
Să aruncăm o lovitură.
Și dacă doriți să încercați, bineînțeles, să o implementați, dar cu siguranță nu trebuie să faceți ceva.
Este un pic mai complicat daca vrei ca pseudo-codul sa te ajunga acolo altfel in urmatorul videoclip voi merge mai
departe si sa construiesc.