De ce contează?
Imaginează-ți rețeaua de drumuri ca pe un set de arcuri întinse între orașe: fiecare arc are o „tensiune" — costul muchiei. La început nu știi cât e de departe fiecare oraș, așa că presupui infinit. Apoi te plimbi peste TOATE arcurile, iar și iar, și de fiecare dată relaxezi tensiunea: dacă printr-un arc ajungi mai ieftin într-un oraș, cobori estimarea. După destule treceri, tensiunile se liniștesc — distanțele nu mai scad. Asta e Bellman-Ford.
Intuiția
Nu cauți drumul minim direct. Pleci de la o estimare grosolană (dist[sursă]=0,
restul infinit) și o îmbunătățești treptat. O singură operație, repetată mult:
relaxarea. Pentru o muchie (u, v, c), dacă „ajung la u și mai adaug c"
e mai ieftin decât estimarea curentă a lui v, atunci cobor dist[v]. Repeți
relaxarea pe toate muchiile până când nimic nu mai scade — și acolo te oprești.
De ce se oprește garantat? După trecerea k, toate drumurile minime cu cel
mult k muchii sunt deja corecte. Un drum minim simplu are cel mult n-1
muchii, deci n-1 treceri ajung întotdeauna. Iar dacă trecerea a n-a ÎNCĂ
schimbă ceva, singura explicație e un ciclu negativ — distanțele ar scădea
la nesfârșit.