3. diel - Hľadanie najkratšej cesty v grafe

V minulej lekcii, Náhodný priechod grafom, priechod do hĺbky a do šírky , sme sa naučili nejako prechádzať graf. V reálnej situácii to je ale trochu zložitejšia. Graf obsahuje hromadu kružníc a ohodnotené hrany. Na druhú stranu sme schopní pomocou grafov riešiť reálne problémy. Jeden z prvých problémov je hľadanie najkratšej cesty. Prečo nepoužiť jednoduché BFS?

BFS

Z článku o vlne poznáme algoritmus prehľadávanie do šírky. Ten algoritmus je skvelý, nemožno ho ale použiť pre graf, kde sú hrany ohodnotené. Prečo? Predstavte si, že by sme mali graf, ktorý vyzerá ako tu na obrázku, alebo sme Lojzko z Nemanice, ktorý chce domov do Palice:

Pri použití BFS by sme si museli všetky cesty nasekať a prechádzať každý stav sám o sebe. Aneb cestu 500 km dlhou by sme museli rozdeliť na 500 dielov a to je veľmi neefektívne, viď obrázok:

Sami si môžeme všimnúť, že jednoduchšie by bolo preskúmať cestu rovno do Palice, alebo to skúsiť vziať cez Kvasnice.

Motivácia zo života

Lojzo robí pre Jesenicko mliekáreň, ktorá rozváža mlieko po celej Českej republike a ktorej vedenie sa rozhodlo pre modernizáciu. Preto poverí Lojza, aby zefektívnil dopravu. Prvou úlohou je nájsť najkratšiu cestu z Jeseníka do každého významného mesta. Lojzo teda vzal ceruzku, papier a písal. Keďže nechcem nikoho uraziť, budem označovať jednotlivé mestá písmenami. Len pre istotu

Pri reálnej situácii bude graf ešte zložitými na. Niekoľko poznámok k tomuto grafu. Pozor na to, že nie je ani veľmi dôležité, ako je graf nakreslený. Dlhé hrany môžu byť ohodnotené malým číslom a krátke veľkým. Jediné, čo graf vizuálne hovorí, je, že sú dva vrcholy spojené. Vieme, odkiaľ kam vrchol vedie a akú má váhu.

A čo je to váha? Môže to byť vzdialenosť, cena, čas dojazdu medzi dvoma mestami ... To záleží od účelu. Pre potreby firmy sa asi oplatí ohodnotiť si hrany cenou, tj. Koľko ich bude stáť jazda medzi A a B. Niekedy totiž môže dlhšiu cesta vyjsť lacnejšie, napr. Preto, že nie je cez spoplatnenú komunikáciu. V našom prípade to sú zatiaľ len vzdialenosti.

Dijkstrov algoritmus

Dijkstrov algoritmus je najpopulárnejší a najpoužívanejší algoritmus na hľadanie najkratšej cesty v grafe. Myšlienka je jednoduchá. Chceme najkratšiu cestu z jedného uzla do všetkých ostatných (tým pádom nájdeme aj cestu z A do B). Zadáme počiatočný uzol a ideme. Implementáciu ako takú nájdete v článku Implementácia Dijkstrova algoritmu.

Teraz si popíšeme iba algoritmus.

Vstup

Vstupom je ohodnotený graf G a počiatočné uzol s (štart).

Výstup

Výstupy je pole vzdialenosťou, udávajúce najkratšej vzdialenosti medzi uzlom s a všetkými ostatnými a polia predchodcov.

Opis algoritmu

Pro každý vrchol v:
    // máme 3 stavy vrcholů - nenalezený, otevřený, uzavřený
    stav(v) = nenalezený
    ohodnocení(v) = nekonečno (v našem případě třeba 999999 nebo INTEGER.MAX či tak...)
    Předchůdci_vrcholu(v) = null      // chceme si pamatovat cestu, kudy jdeme, zde je prázdná
stav(s) = otevřený
ohodnoceni(s) = 0
Dokud existují nějaké otevřené vrcholy:
    Vezměme otevřený vrchol v, jehož ohodnocení(v) je minimální
    Pro všechny následníky w vrcholu v:
          Pokud (ohodnocení(w) > ohodnocení(v) + vzdálenost(v, w)):
            ohodnocení(w) = ohodnocení(v) + vzdálenost(v, w)
            stav(w) = otevřený
            Předchůdci_vrcholu(w).přidej(v)        // přidáme vrchol do předchůdců
        stav(v) = uzavřený   // všechny jeho sousedy jsme už prošli

Ukážka

Pokiaľ vám pseudokód nič nehovorí, ukážeme si postup na jednoduchom grafe, ako to vyzerá v praxi. Laicky povedané, chceme do jednotlivých vrcholov dostať informáciu, ako sa do nich najkratšou cestou dostaneme.

Pritom si treba uvedomiť, že ak poznáme cestu napr. Z Olomouca do Chebu, nepoznáme automaticky cestu z Chebu do Olomouca ... Na to pozor!

Krok 0, inicializácia:

Krok 1, prejdeme všetky mestá, ktoré sú dosiahnuteľná z vrcholu J. Prechádzame od najmenšej vzdialenosti:

Krok 2, teraz prejdeme jednotlivé vrcholy podľa poradia, v akom sme ich prechádzali. Vidíme, že sa nám zmenilo mesto A, našli sme kratšiu cestu:

Krok 3, ďalej pokračujeme intuitívne tak, ako sme pokračovali doteraz:

Krok 4, sme v cieli. Máme najkratšiu cestu do všetkých miest v zadanom grafe:

Pozor, graf nesmie mať záporný cyklus. Čiže, keď prejdeme cyklom, nesmie byť výsledná cesta záporná. Algoritmus sa totiž zacyklí, lebo zakaždým nájde kratšie a kratšie cestu ... Bohužiaľ, čo sa týka samotných záporných hrán, nie je jasné, ako sa Dijkstra zachová. Záleží na implementáciu. Kvôli týmto problémom existuje algoritmus Bellman-Ford.

Bellman-Ford

Čo keď cez ČR tiahnu piráti, ktorí sa usídlili na niektorých dopravných tepnách. Je všeobecne známe, že piráti milujú mlieko a veľmi radi nakupujú od poctivé mliekarne. Preto, keď pôjdeme cez cestu s pirátmi, bude tá cesta zárobková, pretože sa zbavíme časti zásob rovno na ceste. Máme teda v grafe naraz zápornej ohodnotenie hrany, pretože cena cesty je záporná, pretože za ňou dostaneme zaplatené. Lojzo teda s nadšením sadne k PC a prepíše Dijkstra tak, aby riešil aj pirátmi:

Vstup

Vstupom je ohodnotený graf G a počiatočné uzol s (štart).

Výstup

Výstupy je pole vzdialenosťou, udávajúce najkratšej vzdialenosti medzi uzlom s a všetkými ostatnými a polia predchodcov. Ďalším výstupom je detekcia záporného cyklu.

Opis algoritmu

Pro každý vrchol v :
        ohodnocení(v) = nekonečno
    předchůdci_vrcholu[v] = null // chceme si pamatovat cestu, kudy jdeme, zde je prázdná
ohodnoceni(s) = 0

pro každý další vrchol u
    pro každý vrchol v
        pokud ohodnocení (u) + vzdálenost(u,v) < ohodnocení(v)
            ohodnoceni(v) = ohodnocení (u) + vzdálenost(u,v)
            předchůdce_vrcholu(v).add(u)

Pro každý vrchol u
    pro každý vrchol v
        pokud ohodnocení (u) + vzdálenost(u,v) < ohodnocení(v)
                      vypis "ERROR, zaporny cyklus"

Znie to možno ako mágia, ale skúsme si rozobrať hlavnú myšlienku. Každá záporná hrana nám môže pohnúť s naším doterajším výpočtom, preto musíme iterovat toľkokrát, koľko máme vrcholov - 1 (prvý vrchol má vzdialenosť 0).

Ukážka

V našom upravenom prípade by to mohlo vyzerať nejako takto.

Krok 0, inicializácia:

Krok 1, teraz pozor - robíme niečo trochu iné ako u Dijkstra. Pre každý vrchol skúsime, či máme zlepšujúce cestu. Tu by sa mohlo zdať, že záleží na poradí. Ak skúsime zlé poradí, cesta sa o moc nezlepší. Je však dôležité, že po V (počet vrcholov) -1 opakovaniach algoritmus vždy nájde správne riešenie, nehľadiac na poradie:

Krok 2, opätovný priechod grafom:

Krok 3, to isté:

Krok 4, vzhľadom na to, že musíme urobiť V - 1 krokov, tak krok 4 vyzerá rovnako ako krok 3, len skontrolujeme, ze je všetko OK:

Tento algoritmus nám dokonca oznámi chybu, pokiaľ je v grafe záporný cyklus. Oproti Dijkstra vieme, že Bellman-Ford urobí vždy V * E krokov (pre V = počet vrcholov a E = počet hrán). Ak aj potom existuje kratšia cesta, je v grafe záporný cyklus.

Floyd-Warshallův algoritmus

Zadanie bolo úspešné a Lojzo firme vyniesol veľké peniaze. Piráti nakupovali mlieko ako šialení. Preto sa vedenie rozhodlo, že rozšíri pôsobnosť a v každom meste si založili vlastnú pobočku. Lojzo dostal ďalšiu úlohu. Firma po ňom chce, aby našiel najkratšej cesty medzi všetkými mestami navzájom. Na to sa hodí Floyd-Warshallův algoritmus. Tento algoritmus je veľmi jednoduchý, elegantný a bohužiaľ aj časovo náročný. Sú to vlastne tri for -cykly v sebe. Keď si predstavíte maticu, tak pre každú dvojicu vrcholov zisťuje, či nie je bližšie nejaká cesta cez tretiu vrchol.

Vstup

Hodnotený graf G

Výstup

matica vzdialeností

Opis algoritmu

pro každé k od 1 do n
     pro každé i od 1 do n
      pro každé j od 1 do n
        pokud G[i][j] > G[i][k] + G[k][j] potom
            G[i][j] = G[i][k] + G[k][j]

Tento algoritmus nie je možné ukázať pomocou grafov ako predchádzajúci algoritmy. Namiesto toho použijeme maticu vzdialeností = matice susednosti, kde je 0 a 1 pre označenie susednosti medzi mestami.

Nákupný algoritmov

Teraz prichádza tá najdôležitejšia časť. Aký algoritmus kedy použiť? K tomu slúži nasledujúca tabuľka:

test	Dijkstra	Bellman-Ford	Floyd-Warshall
zložitosť	O (E * log (V))	O (V * E)	O (V 3)
Najkratšia cesta z A do B	áno	áno	áno
Najkratšia cesta medzi všetkými vrcholmi	nie	nie	áno
Berie aj záporné hrany	nie *	áno	áno
Môže mať záporný cyklus	nie	nie	nie

• Nie je jasné, ako to algoritmus rieši, záleží na implementáciu.

Kedy aký algoritmus teda použiť? Ide zas o to, čo vlastne chceme robiť. Najčastejšie je Dijkstrov algoritmus, kedy chceme len z jedného uzla niekam. Ak chceme zo všetkých vrcholov do všetkých, implementujeme Floyd-Warshalla.

Malé cvičeníčko na záver - Čo sa stane, keď týmto algoritmom dáme záporné cykly? Aká je najkratšia cesta cez záporný cyklus?

Odpoveď leží v článku

V ďalšej lekcii, Tok v sieti a Dinicův algoritmus na hľadanie maximálneho toku , si ukážeme definície toku v sieti, súvisiacich pojmov a implementácia jedného z algoritmov na hľadanie maximálneho toku zvaného Dinicův algoritmus.

 

Mal si s čímkoľvek problém? Stiahni si vzorovú aplikáciu nižšie a porovnaj ju so svojím projektom, chybu tak ľahko nájdeš.