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

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