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

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

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':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.

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.

h3. Etape de rezolvare