BF - Easter Office week
Tento týden až 80% sleva na e-learning MS Office!
80 % bodů zdarma díky naší Velikonoční akci!

Lekce 3 - Hledání nejkratší cesty v grafu

V minulé lekci, Náhodný průchod grafem, průchod do hloubky a do šířky, jsme se naučili nějak procházet graf. V reálné situaci to je ale trochu složitější. Graf obsahuje hromadu kružnic a ohodnocené hrany. Na druhou stranu jsme schopni pomocí grafů řešit reálné problémy. Jeden z prvních problémů je hledání nejkratší cesty. Proč nepoužít jednoduché BFS?

BFS

Z článku o vlně známe algoritmus prohledávání do šířky. Ten algoritmus je skvělý, nelze jej ale použít pro graf, kde jsou hrany ohodnocené. Proč? Představte si, že bychom měli graf, který vypadá jako tady na obrázku, aneb jsme Lojzík z Nemanic, který chce domů do Palice:

Hledání nejkratší cesty v grafu

Při použití BFS bychom si museli všechny cesty nasekat a procházet každý stav sám o sobě. Aneb cestu 500 km dlouhou bychom museli rozdělit na 500 dílů a to je velmi neefektivní, viz obrázek:

Použití šíření do šířky na hledání nejkratší cesty v grafu

Sami si můžeme všimnout, že jednodušší by bylo prozkoumat cestu rovnou do Palice, nebo to zkusit vzít přes Kvasnice.

Motivace ze života

Lojza dělá pro Jesenickou mlékárnu, která rozváží mléko po celé České republice a jejíž vedení se rozhodlo pro modernizaci. Proto pověří Lojzu, aby zefektivnil dopravu. Prvním úkolem je najít nejkratší cestu z Jeseníku do každého významného města. Lojza tedy vzal tužku, papír a psal. Jelikož nechci nikoho urazit, budu označovat jednotlivá města písmeny. Jen pro jistotu :)

BFS

Při reálné situaci bude graf ještě nepřehlednější. Několik poznámek k tomuto grafu. Pozor na to, že není ani moc důležité, jak je graf nakreslený. Dlouhé hrany mohou být ohodnoceny malým číslem a krátké velkým. Jediné, co graf vizuálně říká, je, že jsou dva vrcholy spojené. Víme, odkud kam vrchol vede a jakou má váhu.

A co je to váha? Může to být vzdálenost, cena, čas dojezdu mezi dvěma městy... To záleží na účelu. Pro potřeby firmy se asi vyplatí ohodnotit si hrany cenou, tj. kolik je bude stát jízda mezi A a B. Někdy totiž může delší cesta vyjít levněji, např. proto, že není přes zpoplatněnou komunikaci. V našem případě to jsou zatím jen vzdálenosti.

Dijkstrův algoritmus

Dijkstrův algoritmus je nejpopulárnější a nejpoužívanější algoritmus na hledání nejkratší cesty v grafu. Myšlenka je jednoduchá. Chceme nejkratší cestu z jednoho uzlu do všech ostatních (tím pádem najdeme i cestu z A do B). Zadáme počáteční uzel a jedeme. Implementaci jako takovou najdete v článku Implementace Dijkstrova algoritmu.

Nyní si popíšeme pouze algoritmus.

Vstup

Vstupem je ohodnocený graf G a počáteční uzel s (start).

Výstup

Výstupy je pole vzdáleností, udávající nejkratší vzdálenosti mezi uzlem s a všemi ostatními a pole předchůdců.

Popis 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ázka

Pokud vám pseudokód nic neříká, ukážeme si postup na jednoduchém grafu, jak to vypadá v praxi. Laicky řečeno, chceme do jednotlivých vrcholů dostat informaci, jak se do nich nejkratší cestou dostaneme.

Přitom je třeba si uvědomit, že pokud známe cestu např. z Olomouce do Chebu, neznáme automaticky cestu z Chebu do Olomouce... Na to pozor!

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

Krok 0, inicializace:

Dijkstrův algoritmus – Krok 0

Krok 1, projdeme všechna města, která jsou dosažitelná z vrcholu J. Procházíme od nejmenší vzdálenosti:

Dijkstrův algoritmus – Krok 1

Krok 2, nyní projdeme jednotlivé vrcholy podle pořadí, v jakém jsme je procházeli. Vidíme, že se nám změnilo město A, našli jsme kratší cestu:

Dijkstrův algoritmus – Krok 2

Krok 3, dále pokračujeme intuitivně tak, jak jsme pokračovali doposud:

Dijkstrův algoritmus – Krok 3

Krok 4, jsme u cíle. Máme nejkratší cestu do všech měst v zadaném grafu:

Dijkstrův algoritmus – Krok 4

Pozor, graf nesmí mít záporný cyklus. Neboli, když projdeme cyklem, nesmí být výsledná cesta záporná. Algoritmus se totiž zacyklí, neboť pokaždé najde kratší a kratší cestu... Bohužel, co se týče samotných záporných hran, není jasné, jak se Dijkstra zachová. Záleží na implementaci. Kvůli těmto problémům existuje algoritmus Bellman-Ford.

Bellman-Ford

Co když přes ČR táhnou piráti, kteří se usídlili na některých dopravních tepnách. Je všeobecně známo, že piráti milují mléko a velmi rádi nakupují od poctivé mlékárny. Proto, když pojedeme přes cestu s piráty, bude ta cesta výdělečná, neboť se zbavíme části zásob rovnou na cestě. Máme tedy v grafu najednou záporné ohodnocení hrany, neboť cena cesty je záporná, protože za ní dostaneme zaplaceno. Lojza tedy s nadšením sedne k PC a přepíše Dijkstru tak, aby řešil i piráty:

Vstup

Vstupem je ohodnocený graf G a počáteční uzel s (start).

Výstup

Výstupy je pole vzdáleností, udávající nejkratší vzdálenosti mezi uzlem s a všemi ostatními a pole předchůdců. Dalším výstupem je detekce záporného cyklu.

Popis 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"

Zní to možná jako magie, ale zkusme si rozebrat hlavní myšlenku. Každá záporná hrana nám může hnout s naším dosavadním výpočtem, proto musíme iterovat tolikrát, kolik máme vrcholů - 1 (první vrchol má vzdálenost 0).

Ukázka

V našem upraveném případě by to mohlo vypadat nějak takto.

Krok 0, inicializace:

Algoritmus Bellman-Ford – Krok 0

Krok 1, nyní pozor - děláme něco trochu jiného než u Dijkstry. Pro každý vrchol zkusíme, jestli máme zlepšující cestu. Zde by se mohlo zdát, že záleží na pořadí. Pokud zkusíme špatné pořadí, cesta se o moc nezlepší. Je však důležité, že po V (počet vrcholů) -1 iteracích algoritmus vždy najde správné řešení, nehledě na pořadí:

Algoritmus Bellman-Ford – Krok 1

Krok 2, opětovný průchod grafem:

Algoritmus Bellman-Ford – Krok 2

Krok 3, to samé:

Algoritmus Bellman-Ford – Krok 3

Krok 4, vzhledem k tomu, že musíme udělat V - 1 kroků, tak krok 4 vypadá stejně jako krok 3, jen zkontrolujeme, ze je vše OK:

Algoritmus Bellman-Ford – Krok 4

Tento algoritmus nám dokonce oznámí chybu, pokud je v grafu záporný cyklus. Oproti Dijkstrovi víme, že Bellman-Ford udělá vždy V * E kroků (pro V = počet vrcholů a E = počet hran). Pokud i potom existuje kratší cesta, je v grafu záporný cyklus.

Floyd-Warshallův algoritmus

Zadání bylo úspěšné a Lojza firmě vynesl velké peníze. Piráti nakupovali mléko jako šílení. Proto se vedení rozhodlo, že rozšíří působnost a v každém městě si založili vlastní pobočku. Lojza dostal další úkol. Firma po něm chce, aby našel nejkratší cesty mezi všemi městy navzájem. Na to se hodí Floyd-Warshallův algoritmus. Tento algoritmus je velmi jednoduchý, elegantní a bohužel také časově náročný. Jsou to vlastně tři for-cykly v sobě. Když si představíte matici, tak pro každou dvojici vrcholů zjišťuje, jestli není bližší nějaká cesta přes třetí vrchol.

Vstup

Ohodnocený graf G

Výstup

Matice vzdáleností

Popis 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 není možné ukázat pomocí grafů jako předchozí algoritmy. Místo toho použijeme matici vzdáleností = matice sousednosti, kde je 0 a 1 pro označení sousednosti mezi městy.

Porovnání algoritmů

Nyní přichází ta nejdůležitější část. Jaký algoritmus kdy použít? K tomu slouží následující tabulka:

Test Dijkstra Bellman-Ford Floyd-Warshall
Složitost O(E*log(V)) O(V*E) O(V3)
Nejkratší cesta z A do B Ano Ano Ano
Nejkratší cesta mezi všemi vrcholy Ne Ne Ano
Bere i záporné hrany Ne* Ano Ano
Může mít záporný cyklus Ne Ne Ne

* není jasné, jak to algoritmus řeší, záleží na implementaci.

Kdy jaký algoritmus tedy použít? Jde zas o to, co vlastně chceme dělat. Nejčastější je Dijkstrův algoritmus, kdy chceme jen z jednoho uzlu někam. Pokud chceme ze všech vrcholů do všech, implementujeme Floyd-Warshalla.

Malé cvičeníčko na závěr - Co se stane, když těmto algoritmům dáme záporné cykly? Jaká je nejkratší cesta přes záporný cyklus?

Odpověď leží v článku :)


 

Stáhnout

Staženo 6x (4.71 kB)
Aplikace je včetně zdrojových kódů

 

 

Článek pro vás napsal Tricerator
Avatar
Jak se ti líbí článek?
Ještě nikdo nehodnotil, buď první!
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Předchozí článek
Náhodný průchod grafem, průchod do hloubky a do šířky
Všechny články v sekci
Grafové algoritmy
Aktivity (7)

 

 

Komentáře

Avatar
Jakub Hrubčo:15.12.2019 13:40

Niesom si isty, ci tomu rozumiem, ale v pseudokode Dijkstrovho algoritmu by nemal byt posledny riadok stav(v)=uzavreny mimo cyklu, ktory prechadza vsetkych nasledovnikov?

 
Odpovědět
15.12.2019 13:40
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Tricerator
Lektor
Avatar
Odpovídá na Jakub Hrubčo
Tricerator:18.12.2019 0:20

Mas pravdu, vloudil se mi tam sotek. Rozhodne musi byt mimo cyklus, jinak by to nemelo smysl. Diky!

Odpovědět
18.12.2019 0:20
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.