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

*** 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:
 
La fiecare dintre cei k pasi.
Extragem din heap, O(log(k * n))
Reconstituim drumul, O(n * n) (il calculam iarasi)
Blocam nodurile de la start pana la nodul de deviatie, O(n)
 
Pentru fiecare dintre cele maxim n noduri din drum:
Vedem cel mai scurt drum de continuare, O(n * n)
Il adaugam in heap, O(log(k * n))
 
Complexitatea ajunge acum la O(k * n * (n * n + log(k * n))), aproximativ O(k * n^3). Iarasi, algoritmul se comporta mai bine in practica decat pare in complexitate.

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:

Observatii, indicatii, completari

* La fiecare dintre cei $k$ pasi.
** Extragem din heap, $O(log(k * n))$
** Reconstituim drumul, $O(n * n)$ (il calculam iarasi)
** Blocam nodurile de la start pana la nodul de deviatie, $O(n)$
** Pentru fiecare dintre cele maxim $n$ noduri din drum:
*** Vedem cel mai scurt drum de continuare, $O(n * n)$
*** Il adaugam in heap, $O(log(k * n))$

Algoritmul poate fi mai incet sau mai rapid. Se poate folosi ceva mai simplu de implementat in loc de heap, sau un algoritm de drumuri minime mai evoluat. Daca va intrebati daca algoritmul poate fi folosit pentru a determina un drum hamiltonian, raspunsul este da, dar asta necesita determinarea tuturor drumurile lor dintre 2 muchii, care este exponential in functie de n.

Complexitatea ajunge acum la {$O(k * n * (n * n + log(k * n)))$}, aproximativ {$O(k * n^3^)$}. Iarasi, algoritmul se comporta mai bine in practica decat pare in complexitate.

Daca sunteti interesati si, bineinteles, daca "va tine", incercati se rezolvati problema [1]SGU 145 , de unde a pornit de fapt acest articol. Se cere cazul cel dificil, cu drumuri elementare.

h2. Observatii, indicatii, completari

References

Algoritmul poate fi mai incet sau mai rapid. Se poate folosi ceva mai simplu de implementat in loc de heap, sau un algoritm de drumuri minime mai evoluat. Daca va intrebati daca algoritmul poate fi folosit pentru a determina un drum hamiltonian, raspunsul este da, dar asta necesita determinarea tuturor drumurile lor dintre $2$ muchii, care este exponential in functie de {$n$}.

Visible links
1. http://acm.sgu.ru/problem.php?contest=0&problem=145

Daca sunteti interesati si, bineinteles, daca "va tine", incercati se rezolvati problema "SGU 145":http://acm.sgu.ru/problem.php?contest=0&problem=145 , de unde a pornit de fapt acest articol. Se cere cazul cel dificil, cu drumuri elementare.

3695