Marmelada

Folosind o parcurgere in latime vom calcula drumul minim de la S la D. Fie K lungimea acestui drum minim. Apoi sortam sirul initial de costuri si realizam o bijectie intre muchiile din drumul minim si primele K costuri din sirul sortat. Restul muchiilor le putem atribui orice cost din cele ramase disponibile. Este clar ca in acest fel obtinem cel mai scurt drum posibil intre S si D, deoarece nu exista un drum mai scurt de K muchii intre S si D si pentru acest drum de lungime K orice atribuire de costuri muchiilor poate genera doar un drum cel mult egal cu cel calculat. Complexitatea va fi deci O(M*logM+N).