h1(#retea). 'Retea':problema/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( C[k][j - q] + Cm[i][k] / 2^q^ )$ 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.

Vom construi 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( C[k][j - q] + Cm[i][k] / 2^q^ )$ 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. Pentru a gasi drumul minim intre nodul initial si cel final folosim Dijkstra cu heapuri pentru complexitatea optima. Bellman-Ford nu intra in timp.

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

Solutia aceasta are complexitate $O(M * K * K * log(N * K))$. Chiar daca pare mare complexitatea, aceasta este supraestimata.