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
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ă.
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.
