h2. Exemplu
table(example). |_. bellmanford.in |_. bellmanford.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|5 8
1 3 -3
1 5 7
3 2 -2
3 4 7
5 1 4
5 2 3
5 3 4
4 5 3
| -5 -3 4 7

|

h3. Explicaţie

h2. Soluţie

...

Drumul de cost minim într-un graf de la o sursă la celelalte noduri se poate determina în complexitate O(M log N) folosind algoritmul lui Dijkstra. Totuşi, acest algoritm necesită costuri pozitive pe muchii, deci nu va ajuta la rezolvarea acestei probleme. În acest caz, se foloseşte algoritmul Bellman-Ford. Spre deosebire de Dijkstra, care foloseşte muchiile o singură dată pentru îmbunătăţirea costului, Bellman-Ford foloseşte fiecare muchie de N-1 ori, repetarea asigurând propagarea distanţei minime prin graf. Algoritmul permite detectarea ciclurilor de cost negativ, aparând în cazul în care, după cele N-1 repetiţii, există o muchie care îmbunătăţeşte costul vreunui nod.
 
h3. Etape de rezolvare
 
O soluţie brute-force de complexitate O(N*M) obţine 50 puncte. Se deduce imediat o îmbunătăţire a algoritmului: în cazul în care costul unui nod nu a fost îmbunătăţit, folosirea muchiilor care pornesc din el este inutilă. Astfel, se poate ţine o listă a nodurilor îmbunăţite, la fiecare pas scoţâd un element din aceasta. Se va încerca îmbunătăţirea costului nodurilor vecine, în caz introducându-le în listă dacă nu apar. Această listă se poate implementa printr-un heap, nodurile cu cost minim având prioritate, soluţia rulând chiar mai greu decât brute-force-ul, obţinând 35 de puncte, sau printr-o coadă, soluţia obţinând 100 de puncte.

== include(page="template/taskfooter" task_id="bellmanford") ==