(Creat de '_fluffy_':user/fluffy la data de _2004-11-29_ categoria _Grafuri_, autor(i) _Crestez Leonard_)
*Continut scurt:*

 ==Include(page="template/raw")==
 
Exista un numar mare de algoritmi pentru a calcula cel mai scurt drum intre 2 noduri intr-un graf, dar chiar si al 2-lea cel mai scurt drum este o extindere non-triviala. Vom prezenta un algoritm pentru a afla al k-lea drum minim intre a si b in 2 cazuri, daca drumurile trebuie sa fie elementare sau nu.

 Exista un numar mare de algoritmi pentru a calcula cel mai scurt drum intre 2 noduri intr-un graf, dar chiar si al 2-lea cel mai scurt drum este o extindere non-triviala. Vom prezenta un algoritm pentru a afla al k-lea drum minim intre a si b in 2 cazuri, daca drumurile trebuie sa fie elementare sau nu.

*Continut lung:*

==Include(page="template/raw")==
 

Exista un numar mare de algoritmi pentru a calcula cel mai scurt drum intre 2 noduri intr-un graf, dar chiar si al 2-lea cel mai scurt drum este o extindere non-triviala. Pentru a afla al k-lea drum minim se foloseste un algoritm total diferit fata de cei pentru drum minim. Algoritmul este dificil de implementat, iar sursa rezultata este de obicei voluminoasa, asa ca acest algoritm nu prea intervine in problemele de concurs. Am considerat totusi ca este destul de interesant, si merita prezentat.
O nota importanta este ca nu se determina drumul cu al k-lea cost. Doua drumuri se considera diferita daca au noduri diferite, nu neaparat si cost diferit. Astfel, daca exista 5 drumuri distincte de cost minim, oricare dintre ele poate fi solutie pentru al 4-lea sau al 5-lea drum minim. Astfel, aceasta problema are de fapt mai multe solutii posibile.