- Curent
- Are o distanță
- Muchie folosită
- Drum
- Ciclu negativ
Algoritmul Bellman–Ford
Algoritmul lui Dijkstra greșește când o muchie are lungime negativă, ca un drum care vă plătește o taxă în loc să v-o ceară. Algoritmul Bellman–Ford nu: pur și simplu verifică fiecare muchie din nou și din nou, până când nu se mai îmbunătățește nimic, și poate chiar să-și dea seama când un ciclu face ca distanțele să scadă la nesfârșit. Faceți clic pe un nod ca să porniți din el și parcurgeți trecerile pas cu pas. 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. Fiecare muchie are sens unic, după cum arată săgeata, iar numărul de pe ea este lungimea ei, care poate fi negativă. Faceți clic pe un nod ca să devină start; comutați clicul pe Țintă și faceți clic pe alt nod ca să vedeți la final cel mai scurt drum până la el. Numărul de pe fiecare nod este distanța lui de până acum. Bifați Adaugă un ciclu negativ ca să vedeți cum îl găsește Bellman–Ford. 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 vedea un drum la final, 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.
- Bifați Adaugă un ciclu negativ ca să vedeți cum îl găsește Bellman–Ford. Graf nou creează alt graf de încercat.
Cum funcționează Bellman–Ford
Dați startului distanța 0 și tuturor celorlalte noduri infinit. Apoi faceți treceri: în fiecare trecere verificați o dată fiecare muchie u → v. Dacă u are o distanță și dist(u) plus lungimea muchiei este mai mic decât dist(v), scădeți dist(v) și rețineți u ca drum până acolo. După trecerea k, fiecare drum minim care folosește cel mult k muchii este cunoscut. Un drum minim trece prin fiecare nod cel mult o dată, deci are cel mult n − 1 muchii, iar n − 1 treceri ajung mereu. Dacă o trecere întreagă nu schimbă nimic, căutarea se poate opri mai devreme.
Găsirea unui ciclu negativ
Dacă muchiile unui ciclu însumează mai puțin de zero, încă un tur al lui scurtează mereu un drum, deci nu există deloc un drum minim. Bellman–Ford observă asta: după n − 1 treceri, încă o trecere n-ar trebui să schimbe nimic. Dacă o muchie mai poate fi relaxată, din start se poate ajunge la un ciclu negativ, iar urmând înapoi nodurile reținute de la acea muchie se ajunge în el. În aplicație, ciclul este trasat cu roșu.
Întrebări frecvente
Ce este algoritmul Bellman–Ford?
Un algoritm care găsește drumurile minime de la un start la toate celelalte noduri într-un graf ale cărui muchii pot avea lungimi negative. Relaxează fiecare muchie în treceri repetate și semnalează un ciclu negativ dacă se poate ajunge la el din start.
De ce eșuează algoritmul lui Dijkstra cu muchii negative?
Dijkstra face definitivă distanța unui nod imediat ce acesta 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ă. Bellman–Ford nu face niciodată o distanță definitivă prea devreme; continuă să verifice fiecare muchie.
De ce n − 1 treceri?
Un drum minim nu trebuie niciodată să treacă de două ori prin același nod, deci are cel mult n − 1 muchii. Fiecare trecere prelungește drumurile minime cunoscute cu cel puțin o muchie, deci după n − 1 treceri sunt găsite toate.
Cât de rapid este Bellman–Ford?
Fiecare trecere verifică toate cele E muchii și sunt cel mult V − 1 treceri, deci efortul crește cu V × E. Este mai lent decât algoritmul lui Dijkstra, de aceea Bellman–Ford se folosește când muchiile pot fi negative.
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