NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!
NOVINKA - Online rekvalifikační kurz Java programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.

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

V minulé lekci, Náhodný průchod grafem, průchod do hloubky a do šířky, jsme si ukázali náhodný průchod grafem, průchod do hloubky a do šířky.

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 - Grafové algoritmy

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 - Grafové algoritmy

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 - Grafové algoritmy

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!

Krok 0, inicializace:

Dijkstrův algoritmus – Krok 0 - Grafové algoritmy

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 - Grafové algoritmy

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 - Grafové algoritmy

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

Dijkstrův algoritmus – Krok 3 - Grafové algoritmy

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

Dijkstrův algoritmus – Krok 4 - Grafové algoritmy

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 - Grafové algoritmy

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 - Grafové algoritmy

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

Algoritmus Bellman-Ford – Krok 2 - Grafové algoritmy

Krok 3, to samé:

Algoritmus Bellman-Ford – Krok 3 - Grafové algoritmy

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 - Grafové algoritmy

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 :)

Grafové algoritmy

V další lekci, Tok v síti a Dinicův algoritmus na hledání maximálního toku, si ukážeme definice toku v síti, souvisejících pojmů a implementace jednoho z algoritmů na hledání maximálního toku zvaného Dinicův algoritmus.


 

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.

Stáhnout

Stažením následujícího souboru souhlasíš s licenčními podmínkami

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

 

Předchozí článek
Náhodný průchod grafem, průchod do hloubky a do šířky
Všechny články v sekci
Grafové algoritmy
Přeskočit článek
(nedoporučujeme)
Tok v síti a Dinicův algoritmus na hledání maximálního toku
Článek pro vás napsal Ondřej Michálek
Avatar
Uživatelské hodnocení:
8 hlasů
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.
Aktivity