2.4.2017: zmena souradnic finalky. Korekce pro drive spocitane: N - 0.006, E + 0.018

Jak jsem slibil, podminkou k odloveni tehle kesky NENI opisovani bonusovych cisel z vicek, podminkou dokonce neni ani odlov predchozich dilu serie. Jedine, co budete porebovat, jsou vysledky nekterych prikladu, ktere se v serii objevily.

V tomto dile serie se podivame na zoubek hledani nejkratsi cesty v grafu. To je velmi casto reseny problem i ve vsednim zivote. Napriklad se chcete dostat ze sveho bydliste do sve oblibene hospody, a protoze mate zizen jako tram, chcete tam byt co nejdriv, neboli chcete najit nejkratsi cestu mezi dvema vrcholy v grafu, kde ulice (popr. spoje MHD) jsou hrany a krizovatky (zastavky) vrcholy. Graf je to navic ohodnoceny, nebot cesta kazdou hranou Vam trva urcity cas.

Naplni tohoto dilu bude zejmena Dijkstruv algoritmus, ktery (snad - u te sve o tom obcas pochybuji...) pouziva i Vase GPS pri hledani nejlepsi cesty po silnicich.

Vlna

Na zahrati se podivame na jednoduchy algoritmus - algoritmus "vlny" ("prohledani do sirky").
Tento algoritmus jsme si predstavili v Alg #4 - tam jsme jim obarvovali graf, nyni s jeho pomoci najdeme v neohodnocenem grafu nejkratsi cestu ze zdrojoveho do libovolneho jineho vrcholu.

Budeme k tomu potrebovat frontu, prohledavany graf zadany jako seznam nasledniku a navic jeste budeme chtit, aby si kazdy vrchol "pamatoval" delku nejkratsi cesty do nej; oznacime si ji L(v_i) pro vrchol v_i.

1. Na zacatku nastavime pro vsechny vrcholy L(v) na nekonecno, jen pro start (v₀) plati L(v₀) = 0.
2. Algoritmem popsanym ve ctvrte casti opet sirime "vlnu" grafem, pouze s tim rozdilem, ze kazda dalsi uroven ma vyssi hodnotu L
3. Algoritmus skonci, pokud budou vycerpany vsechny vrcholy nebo pokud vlna dosahne ciloveho vrcholu.

Mame delku nejkratsi cesty S->C. Jak ale zjistime kudy vede? Je to jednoduche - staci couvat z C a postupne vypisovat vrcholy: C, libovolny V, takovy, ze existuje hrana (V, C) a L(V) = L(C)-1, ...., S.

Dijkstruv algoritmus

Dijkstruv algoritmus funguje jak na grafy s ohodnocenymi hranami (musi byt ale nezaporne), tak na neohodnocene (= vsechny hrany maji vahu 1). Je to v podstate jenom slozitejsi verze vlny (samozrejme L(v) nezvysujeme o 1, ale o vahu pouzite hrany) - to, ze normalni vlna nebude v obecnem pripade fungovat, je dobre videt, pokud si vezmete graf, kde neplati trojuhelnikova nerovnost.

Co budeme potrebovat

Chceme opet, aby si kazdy vrchol v pamatoval delku nejkratsi cesty start -> v, dale chceme, aby sel kazdy vrchol oznacit jednim ze trech stavu (funkce St(v)): nenavstiveny (N), navstiveny (Y) a pridany (F).

Algoritmus

1. Inicializace (S = v₀):
   1. pro vsechna v: St(v) = N a L(v) = nekonecno (v pocitaci obvykle nejake dost velke cislo, treba soucet vah vsech hran grafu +1)
   2. St(S) = F, L(S) = 0
   3. vsem sousedum S zmenime stav na Y a urcime L(v) = |(S,v)| (= vaha hrany S->v)
2. Dokud nema cilovy vrchol C stav F, nebo dokud existuji vrcholy stavu Y:
   1. najdeme mezi vrcholy stavu Y vrchol V s nejnizsi hodnotou L(v)
   2. zmenime stav V na F (zafixujeme)
   3. sousedum V se stavem N zmenime stav na Y
   4. sousedum V se stavem Y (vc. tech zmenenych v minulem kroku) prepocitame vzdalenost od S: L(v) = min{L(V) + |(V,v)|, L(v)} (= pokud do v vede kratsi cesta pres V, zmenime L(v))

Takze mame delku nejkratsi cesty S->C, coz je sice samo o sobe uzasne, ale obvykle nam to je bez znalosti te cesty dost na nic (k cemu Vam je, kdyz vite, ze mezi dvema keskami existuje cesta dlouha 200m, kdyz nevite, ktera to je). Tentokrat nejde couvat tak snadno jako u vlny. Musime si do kazdeho vrcholu V ulozit odkaz (cislo, pointer, ...) na vrchol, ze ktereho jsme se do V dostali (posledni vrchol, ktery snizil L(V) pred zmenou St(V) na F). Pak uz to je ovsem snadnejsi nez u vlny - proste jen postupujeme po odkazech od C k S a vypisujeme vrcholy.

Mozna jste jiz nekdy Dijkstruv algoritmus potkali a mel jenom dva stavy (F a N+Y). Tristavovou verzi jsem vybral pro jeji vetsi nazornost.

Dijkstruv algoritmus jde take upravit tak, aby optimalizoval pro vic parametru soucasne.

Priklad:

Cache:

Verim, ze se Vam povedlo predehnat vsechny ostatni lovce FTFek diky skvele zvolene ceste. Ted ale pujde do tuheho. Opraste vedomosti a vrhnete se na predchozi dily algoritmu!
Cislo A je vysledek druheho prikladu Alg#1 (ten s mouchou), B je vysledek druheho prikladu Alg#2 (ten s tunelem), C je vysledek prikladu Alg#3 (tam byl jen jeden) a D je vysledek druheho prikladu Alg#4 (ten s grafem zadanym dvema tabulkami).
(Kontrola: krome D jsou vsechna cisla dvojciferna)

Finalka je na miste, kde se na malem, umele vytvorenem uzemi pres leto dobre dari stepnim bezobratlym. Asi nejcasteji zde muzete v lete potkat saranci modrokridlou nebo svizniky. I okoli je podle me pekne, takze doufam, ze i Vam se bude umisteni kesky libit!

Kes je na souradnicich:
N 49 5(sqrt(A+1)),(A+B+C+D-9)
E 014 (2*L+1),((B-D)^D+18)


Dekuji Tulakovi za upozorneni na chyby ve vzorci!

NECHCI VIDET ZADNE DRIVE-IN LOGY (krome cyklo)!!!

Nelezte do zadneho zakazu vstupu! Na 5 metru od kese se da dojit po pesine!

Za pripadne chyby se predem omlouvam a budu Vam vdecny, kdyz me na ne upozornite.

Provazej Vas Signal!

Zdroje: Algoritmy a programovaci techniky, Wikipedia