Bellman-Ford

Cunoaștem că algoritmul BFS (coada) nu permite determinarea drumurilor de lungime minimă când grafurile au costuri asociate muchiilor (el poate oferi minimul doar luând în calcul numărul de muchii). Într-o secțiune anterioară am prezentat algoritmul lui Dijkstra pentru a fi folosit în cazul când muchiile au asociate costuri.

Algoritmul Bellman-Ford este o îmbunătățire a lui BFS, în sensul că folosește o coadă și un principiu foarte asemănător, diferența fiind că un nod poate ajunge de mai multe ori în coadă (dacă i se actualizează distanța minimă și nu mai este încă în coadă este pus din nou). Timpul de calcul are ordin de complexitate mai slab decât Dijkstra, dar în practică se comportă foarte bine.

Bellman-Ford determină corect drumuri minime și când graful are muchii cu cost negativ și permite detectarea existenței unui ciclu de cost negativ.