h1. Al K-lea drum minim

(Creat de ==user(user="fluffy" type="tiny")== la data de _2004-11-29_ categoria _Grafuri_, autor(i) _Crestez Leonard_)
 
==Include(page="template/raw")==

(Categoria _Algoritmi_, Autor _Leonard Crestez_)

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.

h2. Mod de functionare

Daca pentru drumul minim intre $2$ noduri de obicei se calculeaza drumul minim dintre primul nod si celelalte noduri din graf, pentru a afla al {$k$}-lea drum minim se calculeaza toate primele $k$ drumuri minime, in ordine. Un pas al algortimului consta in aflarea celul de-al {$k$}-lea drum minim cand primele $k$ sunt cunoscute. Drumul minim este folosit de mai multe ori in algoritm, pentru a intelege acest algoritm este necesara o anumita familiaritate cu algoritmul lui Dijkstra.

Daca pentru drumul minim intre $2$ noduri de obicei se calculeaza drumul minim dintre primul nod si celelalte noduri din graf, pentru a afla al {$k$}-lea drum minim se calculeaza toate primele $k - 1$ drumuri minime, in ordine. Un pas al algortimului consta in aflarea celul de-al {$k$}-lea drum minim cand primele $k$ sunt cunoscute. Drumul minim este folosit de mai multe ori in algoritm, pentru a intelege acest algoritm este necesara o anumita familiaritate cu algoritmul lui Dijkstra.

Drumurile minime pana la $k-1$ sunt stocate compactate intr-un arbore de drumuri. Fiecarui nod din acel arbore ii corespunde un nod din graf, dar nu si invers, un nod din graf poate aparea de mai multe ori in arbore. Radacina arborelui corespunde nodului de start, iar toate frunzele arborelui corespund nodului de final, iar drumurile de la radacina catre frunze reprezinta fiecare cate un drum minim. Vezi in figura cum se compacteaza drumurile ({$1, 7, 4, 5$}), ({$1, 7, 3, 5$}), ({$1, 2, 4, 5$}) si ({$1, 2, 6, 4, 5$}). Drumurile sunt primele $4$ drumuri din graful desenat mai sus si luat drept exemplu.

!http://www.infoarena.ro/Al_K_lea_drum_minim?action=download&file=kshortest_graph.png!
!http://www.infoarena.ro/Al_K_lea_drum_minim?action=download&file=kshortest_tree.png!

!Al-K-lea-drum-minim?kshortest_graph.png!
!Al-K-lea-drum-minim?kshortest_tree.png!

Al {$k$}-lea drum minim trebuie sa corespund pana intr-un anumit punct cu un drum aflat deja in arbore, chiar daca punctul acela este de fapt nodul de start. Pentru a gasi urmatorul drum minim, incercam sa "deviem" din fiecare nod din arbore. Un drum de deviatie pentru un anume nod $X$ este un drum identic cu drumul de la radacina pana la nodul {$X$}, care apoi continua (deviaza) pe cel mai scurt drum pana la destinatie care nu a fost inca luat in cosiderare. Spre exemplu pentru nodul $4$ din drumul ({$1, 2, 4, 5$}) putem sa deviem din $4$ prin ({$7, 3, 5$}), formand drumul ({$1, 2, 4, 7, 3, 5$}). Este intuitiv ca, la fiecare pas, pentru fiecare nod din arbore este interesant doar cel mai scurt drum de deviatie.

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 genera doar 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

3695