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.

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.

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.

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

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