Algoritmul Bellman–Ford

Unele probleme de drum minim au muchii care fac un drum mai ieftin: o rambursare, o porțiune la vale, un curs de schimb în favoarea dumneavoastră. Algoritmul lui Dijkstra nu se descurcă cu ele. Algoritmul Bellman–Ford, da, schimbând isteția pe răbdare.

Un graf cu săgeți cu sens unic, câteva muchii negative, distanțele de până acum pe noduri și un ciclu negativ trasat cu roșu
Un graf cu săgeți cu sens unic, câteva muchii negative, distanțele de până acum pe noduri și un ciclu negativ trasat cu roșu

Ideea

Orice algoritm de drum minim se bazează pe o singură mișcare, relaxarea unei muchii: dacă drumul până la u și apoi pe muchia u → v este mai scurt decât cel mai bun drum cunoscut până la v, folosiți-l. Algoritmul lui Dijkstra relaxează fiecare muchie o singură dată, într-o ordine isteață care funcționează doar când nicio muchie nu este negativă. Bellman–Ford nu presupune așa ceva. Relaxează fiecare muchie, în orice ordine fixă, din nou și din nou, până când distanțele nu se mai schimbă.

Pas cu pas

Dați startului distanța 0 și tuturor celorlalte noduri infinit. Repetați de n − 1 ori, pentru n noduri: parcurgeți fiecare muchie u → v și relaxați-o dacă u are o distanță. Opriți-vă mai devreme dacă o trecere întreagă nu schimbă nimic. Apoi mai faceți o trecere. Dacă vreo muchie mai poate fi relaxată, din start se poate ajunge la un ciclu cu total negativ; altfel fiecare distanță este minimă, iar nodurile reținute dau drumurile.

Un exemplu

Luați muchiile cu sens unic A → B de lungime 4, A → C 5, B → D 2 și C → B −3, verificate în această ordine, din A. Trecerea 1 dă B 4, C 5 și D 6, apoi C → B îl scade pe B la 5 − 3 = 2. Trecerea 2 îl scade pe D la 2 + 2 = 4. Trecerea 3 nu schimbă nimic, deci răspunsul este B 2, C 5, D 4. Algoritmul lui Dijkstra l-ar fi făcut definitiv pe B la 4 și pe D la 6, înainte să vadă muchia negativă. Adăugați o muchie D → C de lungime −4, iar ciclul C → B → D → C are totalul −5: fiecare trecere scade din nou distanțele, iar trecerea de verificare semnalează asta.

De ce ajung n − 1 treceri

Un drum minim, când există, nu repetă niciodată un nod, deci are cel mult n − 1 muchii. Relaxarea fiecărei muchii într-o trecere prelungește fiecare drum minim cunoscut corect cu încă o muchie, oricare ar fi ordinea muchiilor. Așadar după trecerea k toate drumurile minime cu cel mult k muchii sunt corecte, iar după n − 1 treceri, toate. Ordinea contează totuși pentru viteză: cu o ordine bună, totul se poate termina în una sau două treceri.

Istorie și utilizări

Alfonso Shimbel a descris metoda în 1955, Lester Ford Jr. în 1956, Edward F. Moore în 1957 și Richard Bellman în 1958; poartă numele a doi dintre ei, Bellman și Ford. Trecerile ei pot fi rulate de fiecare router separat, ceea ce a făcut-o baza protocoalelor de rutare distance-vector precum RIP. În finanțe, logaritmul negativ al cursurilor de schimb transformă o serie profitabilă de schimburi valutare într-un ciclu negativ, pe care Bellman–Ford îl poate găsi.

Richard Bellman în 1962, fotografiat de Alfred Eisenstaedt. A publicat metoda drumurilor minime în 1958, după Shimbel, Ford și Moore.
Richard Bellman în 1962, fotografiat de Alfred Eisenstaedt. A publicat metoda drumurilor minime în 1958, după Shimbel, Ford și Moore.

Explorați

Deschideți aplicația și apăsați Pas. Fiecare muchie are sens unic, iar unele lungimi sunt negative. Fiecare pas verifică o muchie, într-o ordine fixă, iar casetele arată trecerea și câte distanțe a modificat. De obicei, o trecere nu mai schimbă curând nimic și căutarea se oprește mai devreme. Bifați Adaugă un ciclu negativ și urmăriți cum distanțele scad trecere după trecere, până când trecerea de verificare găsește ciclul și îl trasează cu roșu.

Întrebări frecvente

Care este complexitatea în timp a algoritmului Bellman–Ford?

O(V · E) pentru V noduri și E muchii: până la V − 1 treceri, fiecare verificând toate muchiile. Cu oprirea timpurie este adesea mult mai rapid în practică, iar în cel mai bun caz ajunge o singură trecere.

Ce este un ciclu negativ?

Un ciclu ale cărui lungimi ale muchiilor însumează mai puțin de zero. Parcurgându-l iar și iar, un drum devine oricât de scurt, deci distanțele minime până la nodurile la care se ajunge prin el nu sunt definite.

Funcționează Bellman–Ford pe grafuri neorientate?

Doar dacă nicio muchie nu este negativă: o muchie negativă neorientată poate fi parcursă dus-întors, ceea ce este un ciclu negativ de două muchii. Cu muchii nenegative funcționează, dar algoritmul lui Dijkstra este mai rapid.

Ce este SPFA?

Shortest Path Faster Algorithm, o variantă a algoritmului Bellman–Ford care, folosind o coadă, reverifică doar muchiile care pleacă din nodurile a căror distanță tocmai s-a schimbat. Este adesea mult mai rapid, deși cazul cel mai rău este același.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați Bellman–Ford