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:
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:
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
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:
Krok 1, projdeme všechna města, která jsou dosažitelná z vrcholu
J
. Procházíme od nejmenší vzdálenosti:
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:
Krok 3, dále pokračujeme intuitivně tak, jak jsme pokračovali doposud:
Krok 4, jsme u cíle. Máme nejkratší cestu do všech měst v zadaném grafu:
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:
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í:
Krok 2, opětovný průchod grafem:
Krok 3, to samé:
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:
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
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ů