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

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

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 ieşire

În fişierul de ieşire $bellmanford.out$ se va afişa pe prima linie mesajul "$Ciclu negativ!$" dacă în graf există un astfel de ciclu sau, în caz contrar, $N-1$ numere separate printr-un spaţiu. Al $i$-lea număr va reprezenta costul minim al unui lant de la nodul $1$ la nodul $i+1$.

În fişierul de ieşire $bellmanford.out$ se va afişa pe prima linie mesajul "$Ciclu negativ!$" dacă în graf există un astfel de ciclu sau, în caz contrar, $N-1$ numere separate printr-un spaţiu. Al $i$-lea număr va reprezenta costul minim al unui lanţ de la nodul $1$ la nodul $i+1$.

h2. Restricţii

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
 
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.
 
* 'Ciclu':problema/ciclu
 
TODO: Nu prea stiu probleme cu bellman-ford, ar mai trebui adaugate cateva...
 

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