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.