- Curent
- În coadă
- Definitive
- Drum
Algoritmul lui Dijkstra
Algoritmul lui Dijkstra găsește cel mai scurt drum de la un start la fiecare alt nod când muchiile au lungimi, ca drumurile dintre orașe. Se extinde de la start spre exterior, luând mereu cel mai apropiat nod pe care nu l-a terminat încă. Faceți clic pe un nod pentru a porni de la el, alegeți o țintă dacă doriți și avansați pas cu pas pentru a vedea coada, cum scade fiecare distanță când apar drumuri mai scurte și cum apare cel mai scurt drum. Apăsați Redare pentru a urmări căutarea sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Faceți clic pe un nod ca să devină start; comutați clicul pe Țintă și faceți clic pe alt nod pentru a căuta cel mai scurt drum până la el. Numărul de pe fiecare muchie este lungimea ei, numărul de pe fiecare nod este cea mai mică distanță găsită până acum, iar rândul de sub graf este coada, cu cel mai apropiat nod primul. Graf nou creează alt graf; alegeți câte noduri și muchii are. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Faceți clic pe un nod ca să devină start. Pentru a căuta un drum, comutați clicul pe Țintă și faceți clic pe alt nod.
- Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde în căutare.
- Urmăriți coada de sub graf și distanța de pe fiecare nod. Graf nou creează alt graf de încercat.
Cum funcționează algoritmul lui Dijkstra
Dați startului distanța 0 și fiecărui alt nod infinit și puneți startul într-o coadă. Apoi repetați: luați nodul din coadă cu cea mai mică distanță și marcați acea distanță ca definitivă. Pentru fiecare vecin al său care nu este definitiv, adunați lungimea muchiei la distanța nodului. Dacă suma este mai mică decât distanța de până acum a vecinului, ea devine noua distanță, nodul este reținut ca drum până acolo, iar vecinul intră în coadă dacă nu era deja în ea. Când coada este goală, fiecare nod care poate fi atins are distanța minimă.
De ce cel mai apropiat nod este definitiv
Când un nod este cel mai apropiat din coadă, orice alt drum până la el trebuie să iasă din partea terminată a grafului printr-un nod din coadă, care este cel puțin la fel de departe, și apoi să adauge muchii care nu pot fi negative. Deci niciun alt drum nu poate fi mai scurt. De aceea o țintă este sigură abia când este luată din coadă, nu când este atinsă prima dată, și de aceea algoritmul lui Dijkstra eșuează cu muchii negative: acolo este nevoie de algoritmul Bellman–Ford. Când fiecare muchie are lungimea 1, algoritmul lui Dijkstra face același lucru ca o căutare în lățime.
Întrebări frecvente
Ce este algoritmul lui Dijkstra?
O metodă de a găsi cele mai scurte drumuri de la un nod de start la toate celelalte noduri dintr-un graf ale cărui muchii au lungimi de zero sau mai mult. Ia în mod repetat cel mai apropiat nod neterminat, îi face distanța definitivă și îi folosește muchiile pentru a scurta distanțele vecinilor.
De ce nu funcționează algoritmul lui Dijkstra cu muchii negative?
Face distanța unui nod definitivă de îndată ce nodul este cel mai apropiat din coadă. O muchie negativă găsită mai târziu ar putea duce înapoi la acel nod pe un drum mai scurt, deci distanța definitivă ar putea fi greșită. Algoritmul Bellman–Ford se descurcă cu muchii negative, atâta timp cât nu există un ciclu cu suma negativă.
Care este diferența dintre Dijkstra și BFS?
Căutarea în lățime numără muchii și folosește o coadă simplă. Algoritmul lui Dijkstra adună lungimile muchiilor și folosește o coadă de priorități care dă mereu cel mai apropiat nod. Când fiecare muchie are lungimea 1, amândouă găsesc aceleași distanțe.
Cât de rapid este algoritmul lui Dijkstra?
Cu un heap binar drept coadă de priorități, munca crește cu (V + E) log V pentru V noduri și E muchii. Cu un heap Fibonacci este E + V log V. Aplicația ține coada ca listă sortată, ușor de afișat și suficientă pentru grafuri mici.
Este graful meu trimis undeva?
Nu. Graful este creat și parcurs în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor