Jako mnemotechnická pomůcka může posloužit povšimnutí, že v maturitní otázce jsou algoritmy seřazené od nejpomalejšího k nejrychlejšímu – ačkoliv každý dělá něco docela jiného.
Floydův-Warshallův algoritmus slouží k vypočítání vzdáleností (tj. délky nejkratších cest) mezi všemi dvojicemi vrcholů v grafu. Graf je ohodnocený, hodnota každé hrany udává vzdálenost mezi příslušnými vrcholy. Algoritmus bez nejmenších potíží funguje i na orientovaných grafech, potom vzdálenost oběma směry může vyjít různá.
Výsledkem je tabulka NxN čísel, každé udává délku nejkratší cesty mezi dvěma vrcholy. Připomíná to tabulku vzdáleností z autoatlasů. Když žádná cesta mezi danými vrcholy neexistuje, je v tabulce něco jako nekonečno.
Kdybychom si to přáli, můžeme si do tabulky spočítat i první vrchol pro každou cestu; z toho jde snadno nejkratší cestu mezi každými dvěma vrcholy celou vyrobit. Můžete si taky rozmyslet, jak nejkratší cestu najít jen z hotové tabulky vzdáleností.
U maturity by na popis, jak F-W algoritmus funguje, asi už nestačil čas, takže stačí umět říct, co dělá a jak rychle. Povědomí o jeho principu ale může pomoct zapamatovat si jeho časovou složitost.
Základní myšlenka je taková: opakovaně zkoušíme, jestli není cestu mezi dvěma vrcholy rychlejší vzít oklikou přes nějaký třetí vrchol. Naprogramovat se dá úžasně stručně, když výsledky od začátku do konce zaznamenáváme do tabulky. Na začátku si v tabulce poznačíme jen délky hran (tedy to bude matice sousednosti). Pak velkým cyklem projdeme každý vrchol v grafu (označme ho X) a vnitřním cyklem vyzkoušíme cestu mezi každou dvojicí vrcholů AB zkrátit jako AX + XB. Až vyzkoušíme všechna X, máme hotovou tabulku vzdáleností.
Algoritmus se bez potíží srovná i se zápornými délkami hran, pokud je graf orientovaný a neobsahuje záporný cyklus. Cyklus se záporným součtem by ho totiž mohl donutit projít některým vrcholem dvakrát; něco takového už ale není cesta. Když jsou dva vrcholy v obou směrech spojené zápornou hranou, považujeme to taky za záporný cyklus, a stejně se tedy chová každá záporná hrana v neorientovaném grafu.
Cestu mezi každými dvěma vrcholy zkoušíme prodloužit přes každý třetí vrchol. Tady není co vymýšlet, složitost je postě O(N3).
Dijkstrův algoritmus slouží k hledání nejkratších cest z jednoho vrcholu do všech ostatních. Je hezky jednoduchý a docela rychlý, takže ho obvykle použijeme i v případě, že chceme najít jen nejkratší cestu mezi danými dvěma vrcholy. Funguje na orientovaných i neorientovaných grafech, ale hrany musí být nezáporné.
U každého vrcholu si budeme potřebovat ukládat číslo udávající nejmenší dosud známou vzdálenost ze startu.
Aby algoritmus fungoval rychle, potřebujeme haldu s operacemi vlož, vytáhni_nejmenší a sniž_hodnotu. Postačí nám halda z otázky 10, ačkoliv pro tenhle účel není úplně nejrychlejší.
V haldě budou vrcholy řazené právě podle svojí dosud známé vzdálenosti ze startu, od nejbližšího po nejvzdálenější. Na začátku je halda prázdná.
Začneme přirozeně ve vrcholu, ze kterého má hledaná cesta vést; nastavíme mu vzdálenost jako nulovou a dáme ho do haldy.
V každém kroku algoritmu vytáhneme z haldy nejmenší vrchol. Základní předpoklad je, že od té chvíle už se vzdálenost do tohoto vrcholu nemůže nijak zkrátit. Projdeme všechny sousedy tohoto vrcholu (tj. konce hran, které z něj vedou) a zkusíme jim vzdálenost zkrátit jako vzdálenost_do_tohoto_vrcholu + délka_hrany. Když jsme předtím k sousedovi žádnou cestu neznali (tj. vzdalenost byla +∞), přidáme souseda do haldy; když jsme zkrátili nějakou konečnou vzdálenost, musíme na souseda zavolat operaci sniž_hodnotu – kdybychom na změnu vzdálenosti haldu neuporoznili, mohli bychom tím porušit haldové pravidlo.
Algoritmus končí ve chvíli, kdy je halda prázdná. Vzdálenosti ze startu jsou pak už spočítané přesně u všech vrcholů. Když chceme najít cestu ze startu do jediného zadaného vrcholu, můžeme algoritmus skončit už ve chvíli, když ten vrchol táhneme z haldy.
Ukázkový program v Pythonu máte tady.
Předpoklad zmíněný o dva odstavce výše nebude platit, když má některá hrana zápornou délku. V takovém případě Dijkstrův algoritmus opravdu nefunguje; jinak vždy ano.
Každý vrchol nejvýše jednou vložíme do haldy a z haldy vytáhneme. Navíc na něj můžeme při zkoumání (téměř) každé hrany zavolat operaci sniž_hodnotu. Naší binární haldě trvají všechny tři operace O(log(N)) (kde N je aktuální počet vrcholů v haldě, ale v nejhorším případě budou vrcholy v haldě všechny). Složitost tedy odhadneme jako O(N·log(N) + M·log(N)). Můžeme předpokládat, že hran je víc než vrcholů, takže odhad je stručněji jen O(M·log(N)).
Topologické třídění očísluje vrcholy orientovaného grafu tak, aby hrana vedla vždy z vrcholu s nižším číslem do vyššího. Jinými slovy je nějak seřadí do seznamu. Obvykle má taková úloha víc správných řešení; algoritmus prostě najde některé z nich. Když graf obsahuje cyklus, nemá úloha řešení a algoritmus na to přijde. Pracuje s neohodnoceným grafem.
Uplatnění je například, když chceme provést několik úkolů, které mezi sebou ale mají závislosti (například: abych mohl postavit Starport, potřebuju Factory; abych mohl postavit Factory, potřebuju Barracks). Algoritmus vyklopí jedno možné pořadí, v jakém můžeme úkoly provádět.
Zadání se dá zkomplikovat tak, že chceme provést jeden daný úkol a do výsledku nevypisovat žádné, které jsou pro něj zbytečné. Tahle varianta není o moc složitější, ale zatím ji odložíme.
Na začátku si u každého vrcholu spočítáme číslo zvané vstupní stupeň. Je to počet hran, které do vrcholu vedou; stačí projít všechny hrany a koncovým vrcholům přičítat jedničky.
Založíme si seznam vrcholů, které mají vstupní stupeň nulový (bude to asi nějaká fronta nebo zásobník), a odpovídající vrcholy do něj přidáme.
V každém kroku algoritmu vytáhneme jeden vrchol z fronty, vypíšeme ho na výstup a snížíme vstupní stupeň všem vrcholům, do kterých z něj vede hrana. Pokud tím některým sousedům klesl vstupní stupeň na nulu, přidáme je do seznamu.
Algoritmus skončí ve chvíli, když je fronta prázdná. Pokud jsme nezpracovali vrcholy všechny, graf obsahuje cyklus (neboli orientovanou kružnici).
Ukázkový program v Pythonu máte tady.
Každý vrchol zpracujeme nejvýš jednou a každou hranu nejvýš dvakrát (jednou během předzpracování, jednou v hlavním cyklu); můžeme předpokládat, že hran je víc než vrcholů a časová složitost je tedy O(M).
Když máme zadaný jeden vrchol v grafu, který chceme vyřešit (a ostatní odfláknout, jak to jen jde), stačí si předzpracovat vstup a označit si všechny vrcholy, na kterých kýžený úkol závisí.
Nejdřív každému vrcholu spočítáme seznam hran, které do něj vedou – udělá se to podobně, jak jsme počítali vstupní stupeň. Každý vrchol navíc bude mít pravdivostní hodnotu, zda je pro nás zajímavý; na začátku u všech false. Zavedeme si seznam nevyřešených vrcholů, přidáme do něj cílový úkol a zároveň ho označíme jako zajímavý.
Pak vždycky vytáhneme vrchol ze seznamu nevyřešených a podíváme se na všechny vrcholy, ze kterých do něj vede hrana. Ty, které jsme ještě neoznačili jako zajímavé, označíme a zároveň přidáme do seznamu nevyřešených.
Když je seznam nevyřešených vrcholů prázdný, je předzpracování hotové; označili jsme si všechny úkoly, které budeme potřebovat splnit. Stačí proto spustit původní algoritmus a ignorovat přitom vrcholy, které jsme neoznačili jako zajímavé. Přirozeně, cílový vrchol vyjde poslední v pořadí.