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.