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

*Paul:* Ar trebui verificate testele sa nu se ia multe puncte cu Dijkstra.
 

Se dă un graf orientat conex cu $N$ noduri şi $M$ muchii cu costuri. Definim un lanţ ca fiind un şir de noduri cu proprietatea că între oricare două consecutive există o muchie. Costul unui lanţ este dat de suma costurilor muchiilor care unesc nodurile ce îl formează. Definim un ciclu ca fiind un lanţ cu proprietatea că primul element al său este egal cu ultimul.
h2. Cerinţă

h2. Date de intrare

Fişierul de intrare $bellmanford.in$ conţine pe prima linie numerele $N$ şi $M$ cu semnificaţia din enunţ. Pe următoarele $M$ linii se vor afla $3$ numere $A$, $B$ şi $C$ cu semnificaţia că există o muchie de cost $C$ de la nodul $A$ la nodul $B$.

Fişierul de intrare $bellmanford.in$ conţine pe prima linie numerele $N$ şi $M$ cu semnificaţia din enunţ. Pe următoarele $M$ linii se vor afla câte $3$ numere $x$, $y$ şi $c$ cu semnificaţia că există o muchie de cost $c$ de la nodul $x$ la nodul $y$.

h2. Date de ieşire

* $1 ≤ N ≤ 50 000$.
* $1 ≤ M ≤ 250 000$.

* Costurile muchiilor sunt numere întregi cel mult egale in modul cu $1 000$.

* Costurile muchiilor sunt numere întregi cel mult egale în modul cu $1 000$.

h2. Exemplu

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{~2~}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. O demonstraţie a algoritmului există pe 'Wikipedia':http://en.wikipedia.org/wiki/Bellman-ford.

Drumul de cost minim într-un graf de la o sursă la celelalte noduri se poate determina în complexitate $O(M*log{~2~}N)$ folosind 'algoritmul lui Dijkstra':problema/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':http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm. Spre deosebire de algoritmul 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, apărând în cazul în care, după cele $N-1$ repetiţii, există o muchie care îmbunătăţeşte costul vreunui nod. O demonstraţie a algoritmului există pe 'Wikipedia':http://en.wikipedia.org/wiki/Bellman-ford.

h3. Etape de rezolvare

O 'soluţie':job_detail/377448?action=view-source brute-force de complexitate $O(N*M)$ obţine $35$ 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ă de noduri, la fiecare pas scoţând un element din aceasta. Se va încerca îmbunătăţirea costului nodurilor vecine, introducându-le în listă în cazul scăderii costului, dacă nu apar deja. Această listă se poate implementa printr-un heap, selectând la fiecare pas nodul de cost minim, 'soluţia':job_detail/377446?action=view-source obţinând $100$ de puncte, sau printr-o coadă, 'soluţia':job_detail/377445?action=view-source obţinând, de asemenea, $100$ de puncte. Deşi au complexităţi teoretice de $O(N*M*log{~2~}N)$, respectiv $O(N*M)$, cele două soluţii se comportă mult mai bine în practică.
 
h2. Aplicaţii

O 'soluţie':job_detail/381832?action=view-source brute-force de complexitate $O(N*M)$ obţine $35$ 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ă de noduri, la fiecare pas scoţând un element din aceasta. Se va încerca îmbunătăţirea costului nodurilor vecine, introducându-le în listă în cazul scăderii costului, dacă nu apar deja. Această listă se poate implementa printr-un heap, selectând la fiecare pas nodul de cost minim, 'soluţia':job_detail/381833?action=view-source obţinând $100$ de puncte, sau printr-o coadă, 'soluţia':job_detail/381834?action=view-source obţinând, de asemenea, $100$ de puncte. Deşi au complexităţi teoretice de $O(N*M*log{~2~}N)$, respectiv $O(N*M)$, cele două soluţii se comportă mult mai bine în practică.

Determinarea drumului de cost minim reprezintă o subproblemă des întâlnită, astfel că algoritmul Bellman-Ford poate fi folosit cu succes, având performanţe asemănătoare algoritmului lui Dijkstra.

*Paul:* Ar merge chestia asta spusa inainte de capitolul aplicatii (e mai mult mentionare). O aplicatie clasica ar fi flux maxim de cost minim.

h2. Aplicaţii
* 'Flux maxim de cost minim':problema/fmcm
* 'Cuplaj maxim de cost minim':problema/cmcm

* 'Ciclu':problema/ciclu
* 'Lanterna':problema/lanterna

TODO: Nu prea stiu probleme cu bellman-ford, ar mai trebui adaugate cateva...
 

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

4423