Dupa cum am zis mai sus, algoritmul are $2$ variante, daca este necesar ca drumurile sa fie elementare sau nu. Pentru cele $2$ variante se modifica modul in care se calculeaza deviatia minima dintr-un nod. Cazul cel mai simplu este atunci cand nu este necesar ca drumurile sa fie elementare. Pentru nodul $X$ din care trebuie sa deviem, vom lua cel mai scurt drum care inca nu este in arbore. Putem sa calculam de dinainte un arbore de drumuri inversat, de la toate nodurile la destinatie, si sa luam minimul de la nodurile adiacente care NU sunt printre copii in arbore. Pentru arborele din desen, daca ar fi sa deviem din ({$1, 2$}) am putea lua in considerare doar nodul {$1$}.

Daca trebuie sa luam in considerare doar drumurile elementare, algoritmul simplu de mai sus da erori. Spre exemplu, daca ar fi sa deviem din (1, 7) in desen, drumul optim ar fi prin 1, adica (1, 7, 1, 7, 4, 5), care drum nu este elementar. Pentru a scapa de drumurile elementare, este nevoie sa marcam nodurile de la radacina pana la deviatie ca "ocupate" si sa rulam un algoritm de drum minim pana la destinatie. Acest lucru creste foarte mult complexitatea in timp si in implementare.

Daca trebuie sa luam in considerare doar drumurile elementare, algoritmul simplu de mai sus da erori. Spre exemplu, daca ar fi sa deviem din ({$1, 7$}) in desen, drumul optim ar fi prin {$1$}, adica ({$1, 7, 1, 7, 4, 5$}), care drum nu este elementar. Pentru a scapa de drumurile elementare, este nevoie sa marcam nodurile de la radacina pana la deviatie ca "ocupate" si sa rulam un algoritm de drum minim pana la destinatie. Acest lucru creste foarte mult complexitatea in timp si in implementare.
h2. Exemplu
Algoritmul prezentat este destul de complex, asa ca vom detalia rularea algoritmului pe graful din desen. Vom incerca sa calculam toate cele mai scurte $5$ drumuri elementare intre nodurile $1$ si {$5$}. Punem si conditia ca drumurile sa fie elementare (cazul mai dificil).

Exemplu
 
Algoritmul prezentat este destul de complex, asa ca vom detalia rularea algoritmului pe graful din desen. Vom incerca sa calculam toate cele mai scurte 5 drumuri elementare intre nodurile 1 si 5. Punem si conditia ca drumurile sa fie elementare (cazul mai dificil).
 
* Primul drum minim este (1, 7, 4, 5), de lungime 9.
* Incercam sa deviem din 1. Drumul minim de la 1 la 5 care nu trece imediat prin 7 este (1, 2, 4, 5), cu cost 10.
* Incercam sa deviem din 7. Drumul minim de la 7 la 5 care nu trece imediat prin 4 este (7, 3, 5), cu cost 10. Atentie, adaugam si costul de la 1 la 7.
* Incercam sa deviem din 4. Nu exista alt drum de la 4 la 5. Ar putea fi drumul (4, 7, 3, 5), dar nu ar fi elementar, deoarece avem prefixul (1, 7), noduri pe care le-am marcat blocate.
* Din 5 nu are sens sa deviem, asa ca..
* Al doilea drum minim este (1, 2, 4, 5), de lungime 10.
* Incercam sa deviem din 1, dar nu exista drum de la 1 la 5 care sa nu o ia imediat nici prin 2 si nici prin 7.
* Incercam sa deviem din 2. Drumul minim de la 2 la 5 care nu trece imediat prin 4 este (2, 6, 4, 5), cu cost 10. Atentie, drumul trece prin 4, dar nu imediat.
* Incercam sa deviam din 4. Drumul minim de la 4 la 5 care nu trece imediat prin 5 este (4, 7, 3, 5), cu cost 15. Acest drum nu a fost valid mai inainte, dar acum prefixul lui 4 este (1, 2), asa ca drumul e valid.
* Al treilea drum minim este (1, 7, 3, 5), tot de lungime 10. Al doilea si al treilea drum minim sunt interschimbabile.
* Acest drum a fost derivat din 7, asa ca nu trebie incercam sa derivam din 1.
* Incercam sa deviem din 7, dar nu exista drum de la 7 la 5 care sa nu treaca imediat nici prin 3 nici prin 4. Ar fi (7, 1, 2, 4, 5), dar avem 1 ca prefix si marcat blocat. Astfel, evitam un drum neelementar.
* Incercam sa deviem din 3, fara succes(si fara explicatii kilometrice.).
* Al patrulea drum minim este (1, 2, 6, 4, 5), de lungime 11.
* Incercam sa deviem din 2, dar fara succes.
* Incercam sa deviem din 6, dar tot fara succes.
* Incercam sa deviam din 4. Drumul minim de la 4 la 5 care nu trece imediat prin 5 este (4, 7, 3, 5), cu cost 16. Noi am mai gasit odata acest drum, dar de data asta e cu un alt prefix, si alt cost. Drumul complet este (1, 2, 6, 4, 7, 3, 5), nu (1, 2, 4, 7, 3, 5).
* Al cincilea drum minim este (1, 2, 4, 7, 3, 5), de lungime 15.
* Astfel se termina exemplul nostru. Puteti sa incercati, nu mai exista deviatii posibile. Al 6-lea si ultimul drum este (1, 2, 6, 4, 7, 3, 5) , care se intample sa fie si cel mai lung drum, si hamiltonian.
 
Analiza complexitatii
 
Complexitatea algoritmului este diferita in cele 2 variante. In ambele cazuri putem considera la lugimea fiecarui drum este de O(n), si ca heap-ul contine O(k * n) valori. Luam cazul cel mai defavorabil, cu graf complet, si consideram ca un algoritm de drumuri minime necesita timp O(n * n). Astfel, daca nu este nevoie ca drumurile sa fie elementare:
 
Precalculam drumurile de la orice nod la destinatie, O(n * n).
 
La fiecare dintre cei k pasi.
Extragem din heap, O(log(k * n))
Reconstituim drumul, O(n)
 
Pentru fiecare dintre cele maxim n noduri din drum:
Vedem cel mai scurt drum de continuare, O(n)
Il adaugam in heap, O(log(k * n))

* Primul drum minim este ({$1, 7, 4, 5$}), de lungime {$9$}.
* Incercam sa deviem din {$1$}. Drumul minim de la $1$ la $5$ care nu trece imediat prin $7$ este ({$1, 2, 4, 5$}), cu cost {$10$}.
* Incercam sa deviem din {$7$}. Drumul minim de la $7$ la $5$ care nu trece imediat prin $4$ este ({$7, 3, 5$}), cu cost {$10$}. Atentie, adaugam si costul de la $1$ la {$7$}.
* Incercam sa deviem din {$4$}. Nu exista alt drum de la {$4$} la {$5$}. Ar putea fi drumul ({$4, 7, 3, 5$}), dar nu ar fi elementar, deoarece avem prefixul ({$1, 7$}), noduri pe care le-am marcat blocate.
* Din $5$ nu are sens sa deviem, asa ca..
* Al doilea drum minim este ({$1, 2, 4, 5$}), de lungime {$10$}.
* Incercam sa deviem din {$1$}, dar nu exista drum de la $1$ la $5$ care sa nu o ia imediat nici prin $2$ si nici prin {$7$}.
* Incercam sa deviem din {$2$}. Drumul minim de la $2$ la $5$ care nu trece imediat prin $4$ este ({$2, 6, 4, 5$}), cu cost {$10$}. Atentie, drumul trece prin {$4$}, dar nu imediat.
* Incercam sa deviam din {$4$}. Drumul minim de la $4$ la $5$ care nu trece imediat prin $5$ este ({$4, 7, 3, 5$}), cu cost {$15$}. Acest drum nu a fost valid mai inainte, dar acum prefixul lui $4$ este ({$1, 2$}), asa ca drumul e valid.
* Al treilea drum minim este ({$1, 7, 3, 5$}), tot de lungime {$10$}. Al doilea si al treilea drum minim sunt interschimbabile.
* Acest drum a fost derivat din {$7$}, asa ca nu trebie incercam sa derivam din {$1$}.
* Incercam sa deviem din {$7$}, dar nu exista drum de la $7$ la $5$ care sa nu treaca imediat nici prin $3$ nici prin {$4$}. Ar fi ({$7, 1, 2, 4, 5$}), dar avem $1$ ca prefix si marcat blocat. Astfel, evitam un drum neelementar.
* Incercam sa deviem din {$3$}, fara succes(si fara explicatii kilometrice.).
* Al patrulea drum minim este ({$1, 2, 6, 4, 5$}), de lungime {$11$}.
* Incercam sa deviem din {$2$}, dar fara succes.
* Incercam sa deviem din {$6$}, dar tot fara succes.
* Incercam sa deviam din {$4$}. Drumul minim de la $4$ la $5$ care nu trece imediat prin $5$ este ({$4, 7, 3, 5$}), cu cost {$16$}. Noi am mai gasit odata acest drum, dar de data asta e cu un alt prefix, si alt cost. Drumul complet este ({$1, 2, 6, 4, 7, 3, 5$}), nu ({$1, 2, 4, 7, 3, 5$}).
* Al cincilea drum minim este ({$1, 2, 4, 7, 3, 5$}), de lungime {$15$}.
* Astfel se termina exemplul nostru. Puteti sa incercati, nu mai exista deviatii posibile. Al {$6$}-lea si ultimul drum este ({$1, 2, 6, 4, 7, 3, 5$}) , care se intample sa fie si cel mai lung drum, si hamiltonian.
 
h2. Analiza complexitatii
 
Complexitatea algoritmului este diferita in cele $2$ variante. In ambele cazuri putem considera la lugimea fiecarui drum este de {$O(n)$}, si ca heap-ul contine $O(k * n)$ valori. Luam cazul cel mai defavorabil, cu graf complet, si consideram ca un algoritm de drumuri minime necesita timp {$O(n * n)$}. Astfel, daca nu este nevoie ca drumurile sa fie elementare:
 
* Precalculam drumurile de la orice nod la destinatie, {$O(n * n)$}.
* La fiecare dintre cei k pasi.
** Extragem din heap, $O(log(k * n))$
** Reconstituim drumul, $O(n)$
** Pentru fiecare dintre cele maxim $n$ noduri din drum:
*** Vedem cel mai scurt drum de continuare, $O(n)$
*** Il adaugam in heap, $O(log(k * n))$

Complexitatea ajunge astfel la O(k * n * (n + log(k * n))). Trebuie avut in vedere ca in general drumurile minime vor avea noduri relativ putine, asa ca algorimtul e mai rapid decat pare. Daca punem conditia ca drumurile determinate sa fie elementare, complexitatea creste: