h3. Etape de rezolvare

*Paul:* O optimizare la Bellman-Ford-ul clasic e sa te opresti cand la un pas nu a mai fost modificat nici un cost. Ar trebui vazut cat se ia asa.
 

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