Retea

Vom contrui solutia cu programare dinamica astfel: Fie C[i][j] costul minim pentru a ajunge in nodul i cu j acceleratoare folosite. Astfel recurenta va fi urmatoarea C[i][j] = MIN unde k este un vecin al lui i (bineinteles luam toti vecinii posibili), q reprezinta cate acceleratoare folosim pe muchia dintre i si k iar Cm[i][k] reprezinta costul muchiei dintre i si k. Putem observa usor ca aceasta problema este o problema de drum minim intr-un graf in care un nod este reprezentat de perechea (i, j) reprezentand nodul si respectiv numarul de acceleratoare folosite in drumul de la 1 pana la i, iar muchiile grafului intial se transforma in muchii in graful nou luand in calcul "noua dimensiune" data de j, numarul de acceleratoare. Graful nou format nu trebuie retinut propriu zis in memorie, pentru ca muchiile lui sunt usor determinate la fiecare pas din muchiile grafului intial. Avand in vedere cele de mai inainte tot ce trebuie sa facem este un drum minim in noul graf. Facem aceasta cu Dijkstra cu heapuri pentru ca este cel mai rapid si singurul care intra in timp.

Solutia aceasta are complexitate O(M * K * log N).