Přímé procvičení vyložených algoritmů

  1. V následujících grafech najděte nejkratší cestu z vrcholu $A$ do všech ostatních vrcholů. Pokud byste během algoritmu měli na výběr z několika vrcholů, tak si vyberte abecedně menší vrchol. V každém kroku algoritmu (v každé iteraci) vypište hodnoty $\ARRAY{d}{v}$ pro všechny vrcholy $v$. Nakreslete strom nejkratší cesty. 

    1. Použijte Dijkstrův algoritmus.
    2. Použijte Bellman-Fordův algoritmus.
    3. Využijte toho, že první graf jde topologicky uspořádat. V prvním grafu nalezněte nejkratší cestu pomocí algoritmu pro acyklické orientované grafy.
  2. Máme orientovaný graf, jehož jediné záporně ohodnocené hrany jsou ty vedoucí z počátku. Ostatní hrany mají kladné ohodnocení. Bude v takovém grafu fungovat Dijkstrův algoritmus? Dokažte.
  3. Profesor Všezlepšil navrhuje následující algoritmus na hledání nejkratší cesty z $s$ do všech ostatních vrcholů v orientovaných grafech s obecným ohodnocením hran (tedy i záporným): Vezmeme dostatečně velkou konstantu a přičteme ji k ohodnocení každé hrany. Tím získáme nezáporné ohodnocení hran. Potom už můžeme použít Dijkstrův algoritmus. Nalezená nejkratší cesta bude stejná jako nejkratší cesta v grafu s původním ohodnocením.Dokažte, že navrhovaná metoda funguje, nebo nalezněte protipříklad.
  4. (Floyd-Warshall a záporné cykly)
    Ukázali jsme si, že Floyd-Warshallův algoritmus nalezne nejkratší cestu mezi každou dvojicí vrcholů, pokud graf neobsahuje záporný cyklus. Co by se stalo, kdyby graf obsahoval záporný cyklus? 

    Když dostaneme graf, o kterém nevíme, jestli obsahuje záporný cyklus. Nemůžeme pomocí Floyd-Warshallova algoritmu spočítat nejkratší cesty a nebo odpovědět, že graf určitě obsahuje záporný cyklus? Vymyslete, podle čeho to jednoduše poznat.

Varianty problému nejkratší cesty

  1. Dostanete graf a ohodnocení jeho hran. Vaším úkolem je nalézt cestu z vrcholu $s$ do vrcholu $t$ takovou, aby největší ohodnocení hrany na cestě bylo co nejmenší. Tj. vzdálenost $t$ od $s$ po cestě $sPt$ počítáme jako $\max\limits_{e\in P}\{ c(e)\}$.
  2. Dostanete graf jehož hrany jsou ohodnoceny kladnými reálnými čísly. Délka cesty se počítá jako součin ohodnocení hran ležících na cestě, to je $\prod\limits_{e\in sPt} c(e)$.
    1. Najděte nejkratší cestu z vrcholu $s$ do vrcholu $t$. 

      Nápověda: Zkuste převést násobení na sčítání.

    2. Profesor Všezlepšil povídá, že hledání nejkratší cesty není nic složitého. Navrhuje použít Dijkstrův algoritmus, kde nahradíme sčítání násobením (výpočet $\ARRAY{d}{u}+c(uv)$ nahradíme výpočtem $\ARRAY{d}{u}\cdot c(uv)$). Najděte panu profesorovi protipříklad demonstrující, že to tak jednoduše nejde.1
  3. Hledání nejkratší cesty podle několika kritérií je zcela přirozené. Když jedeme někam autem, tak se tam chceme dostat co nejrychleji, ale také chceme najezdit co nejméně kilometrů, abychom zaplatili co nejméně za benzín.
    1. Dostanete graf jehož hrany jsou ohodnoceny uspořádanou dvojicí $(a, b)$. Najděte cestu z vrcholu $s$ do vrcholu $t$ takovou, aby byla nejkratší podle ohodnocení $a$. Pokud by takových cest existovalo více, tak z nich vyberte tu, která je kratší podle ohodnocení $b$. Délku cesty počítáme jako součet ohodnocení hran na cestě po složkách. 
    2. Co kdybychom neměli hrany ohodnocené jen dvojicí, ale trojicí hodnot? Hledáme cestu, která je nejkratší nejprve podle ohodnocení $a$, u cest se stejnou vzdáleností podle $a$ vybereme tu s nejmenší vzdáleností podle $b$ a ze všech cest se stejnou nejmenší vzdáleností podle $a$ i $b$ vybereme tu s nejmenší vzdáleností podle $c$.
  4. Celé Norsko je podkopáno ohromným množstvím tunelů. Před každým tunelem je dopravní značka říkající, jak vysoké auto tunelem projede. Firma sídlící ve městě $X$ rozváží celkem velké, ale hlavně vysoké zakázky, a má s tím pěkný problém. Dobře znají silniční síť a pro každou silnici vědí, jak vysoký náklad tudy provezou a jak je silniční úsek dlouhý.
    1. Firma zná výšku nákladu naloženého na náklaďáku. Nejprve by je zajímalo, jestli vůbec mohou takto vysoký náklad dopravit do města $Y$. Pokud ano, tak by je zajímala nejkratší cesta ze skladu $X$ do cílového místa $Y$. 

      Samozřejmě mohou jezdit jen tak, aby projeli všemi tunely na nalezené cestě a žádný neponičili.

    2. Jaký nejvyšší náklad lze dopravit po silnicích z města $X$ do města $Y$? Pochopte, že čím vyšší zakázku firma vyrobí, tím více vydělá. Na druhou stranu firma musí být schopna dopravit zakázku na místo určení.
  5. Jedete na dovolenou do Norska, protože za vyřešení předchozí úlohy vám norská firma zaplatila dovolenou. Víte odkud vyjíždíte, víte kam jedete a znáte silniční síť. O každé silnici víte, jak je dlouhá a jak rychle po ní lze jet. Můžete si tedy spočítat, za jak dlouho ji projedete. Najděte takovou cestu do cílového místa, abyste tam dorazili co nejrychleji plus mínus $15$min a za druhé, abyste najeli co nejkratší vzdálenost.
  6. Mezi $N$ městy označenými čísly $1$ až $N$ jezdí autobusové linky. Pro každou autobusovou linku dostanete údaje odkud a kam jezdí, a cenu jízdného.
    1. Vypište všechna města, do kterých se lze dostat z města $1$ na nejvýše $2$ přestupy. 
    2. Zjistěte, jak se co nejlevněji dostat z města $1$ do města $N$. Vypište cenu a návod jak přestupovat. Pokud by existovalo více nejlevnějších cest, tak vypište tu s nejmenším počtem přestupů.
    3. Navrhněte program pro autobusovou informační kancelář. Do kanceláře volají jednotliví cestující a ptají se, jak se nejlevněji dostanou z města $X$ do města $Y$. Chtěli bychom jim co nejrychleji odpovědět. Protože jsme slušná informační kancelář, tak v případě, kdy existuje více nejlevnějších cest, chceme zákazníkovi předložit tu s nejmenším počtem přestupů.(Jiná formulace problému je, že dostane $d$ dotazů a máte na ně co nejrychleji odpovědět.)
  7. (Nejspolehlivější cesta)
    Máme rozlehlou počítačovou síť, která je realizována rádiovým spojením. Rádiové spojení může být rušeno jiným vysíláním a tudíž není moc spolehlivé. Síť si reprezentujeme jako orientovaný graf $G=(V,E)$. Ke každé hraně $e\in E$ dostanete ještě číslo $0\leq p(e) \leq 1$, které můžeme interpretovat jako spolehlivost hrany. Číslo $p(e)$ je pravděpodobnost, že informace poslaná z vrcholu $x$ pro hraně $e=xy$ dorazí do $y$ v pořádku (nedojde k chybě). Pokud budeme informace posílat po dvou zřetězených hranách $e,f\in E$, kde $e=xy$ a $f=yz$, tak je pravděpodobnost, že informace vyslané z $x$ dorazí do $z$ v pořádku, rovna $p(e)\cdot p(f)$. Pravděpodobnosti na cestě se násobí. Najděte v zadané síti nejspolehlivější cestu z vrcholu $s$ do vrcholu $t$. Nejspolehlivější cesta je ta s nejmenší pravděpodobností chyby. 
  8. Vrcholy grafu $G=(V,E)$ reprezentují města a hrany reprezentují silnice jednoho podivného království. Silnice vedou vždy z města do města a jinde se nekříží. Pro každou silnici znáte její délku v kilometrech. Máte auto, které má nádrž na $L$ litrů benzínu. Všechna auta v tomto království mají stejnou spotřebu $\sigma$ litrů na $100$km (okamžitá spotřeba je konstantní, ať jezdíte jak jezdíte). Takže s plnou nádrží ujedete nejvýše $K$ kilometrů. Pak vám dojde benzín. Dopravu v tomto království komplikuje to, že jsou benzínové stanice pouze ve městech. Na silnicích žádné nejsou. Proto se při svých cestách musíte omezit na silnice kratší než $K$km.
    1. Navrhněte lineární algoritmus, který zjistí, jestli se svým autem můžete dojet z města $s$ do města $t$.
    2. Bohužel jste zjistili, že se svým starým autem moc daleko nedojedete. Chcete si proto koupit nové auto. Jaká musí být jeho minimální velikost nádrže, abyste byli schopni dojet z $s$ do $t$? Zkuste vymyslet algoritmus pracující v čase $\OO((n+m)\log n)$.

Další algoritmy a speciální případy

  1. Dostanete graf jehož hrany jsou ohodnoceny čísly $1$, $2$,…, $k$. Najděte co nejrychleji nejkratší cestu v tomto grafu.
    1. Dokážete to v čase $\OO(n+km)$? Pro začátek můžete zkusit přemýšlet o případu, kde $k=2$.
    2. A zvládnete najít řešení pracující v čase $\OO((n+m)\log k)$? 

      Nápověda: Kolik různých odhadů vzdálenosti $\ARRAY{d}{v}$ může být v Dijkstrově algoritmu mezi netrvalými vrcholy?

  2. Dostanete orientovaný graf s obecným ohodnocením hran (tedy i se záporným). Máte zaručeno, že nejkratší cesta mezi libovolnou dvojicí vrcholů obsahuje nejvýše $k$ hran. Navrhněte algoritmus, který pro dva vrcholy $u$, $v$ najde nejkratší cestu z $u$ do $v$ v čase $\OO(km)$. Nápověda: Bellman-Ford.
  3. (Yenovo vylepšení Bellman-Fordova algoritmu)
    Nechť $v_1$,…, $v_n$ je nějaké uspořádání vrcholů $V$ takové, že $v_1=s$. Hrany $E$ rozdělíme do dvou skupin $E_1$ a $E_2$, kde $ E_1=\{v_i v_j\,|\, i \lt j\} $ a $ E_2=\{v_i v_j\,|\, i \gt j\} $ (hrany po směru a proti směru uspořádání).
    Ani jedna skupina z $E_1$, $E_2$ nemůže obsahovat orientovaný cyklus (rozmyslete si proč). Dá se tedy říci, že rozdělení hran do skupin odpovídá rozdělení grafu na dva acyklické podgrafy $G_1$, $G_2$. 

    Nyní uspořádáme $E_1$ do posloupnosti ${\cal S}_1$ tak, aby hrana $v_i v_j$ předcházela hraně $v_k v_\ell$ pokud $i\lt k$. Podobně uspořádáme $E_2$ do posloupnosti ${\cal S}_2$ tak, aby hrana $v_i v_j$ předcházela hraně $v_k v_\ell$ pokud $i\gt k$. Hrany $E_1$ jsou v posloupnosti ${\cal S}_1$ v takovém pořadí, abychom postupným voláním procedury update() na hrany z ${\cal S}_1$ našli v podgrafu $G_1$ nejkratší cestu vedoucí z $s$ do všech dostupných vrcholů.

    Nejkratší cesta v $G$ ale může využívat zkratek přes hrany z $E_2$. Proto pro nalezení nejkratší cesty v celém grafu $G$ použijeme Bellman-Fordův algoritmus s posloupností hran ${\cal S}_1, {\cal S}_2, {\cal S}_1, {\cal S}_2, \dots$ Co můžeme říci o potřebném počtu iterací? Jaká bude časová složitost vylepšeného algoritmu?

  4. (Johnsonův algoritmus; využití přípustného potenciálu)
    Dostaneme orientovaný graf, jehož hrany jsou ohodnoceny reálnými čísly (i zápornými). Chtěli bychom pro každou dvojici vrcholů $(x,y)$ najít nejkratší cestu z $x$ do $y$. Dopředu nevíme, jestli graf obsahuje záporný cyklus. 

    Mohli bychom $n$ krát použít Bellman-Fordův algoritmus (celkový čas $\OO(n^2m)$). Nebo bychom mohli pomocí Bellman-Fordova algoritmu zjistit, jestli graf obsahuje záporný cyklus a pak použít Floyd-Warshallův algoritmus (celkový čas $\OO(n^3)$). Třetí možností je následující řešení:

    1. Pomocí Bellman-Fordova algoritmu najdeme nejkratší cestu z libovolného vrcholu do všech ostatních. Při tom spočítáme přípustný potenciál (nebo odpovíme, že neexistuje a skončíme).
    2. Pomocí přípustného potenciálu upravíme ohodnocení hran tak, aby bylo všude nezáporné. (Podívejte se na příklad u metody potenciálu.) 
    3. Nakonec použijeme $(n-1)$ krát Dijkstrův algoritmus na graf s upraveným ohodnocením.

    Rozmyslete si detaily, zdůvodněte správnost algoritmu a určete jeho celkovou časovou složitost.

  5. (Gabow’s scaling algorithm) Scaling algorithm se do češtiny překládá jako algoritmus měnící měřítko. Algoritmus se dá použít pouze pro grafy, jejichž hrany jsou ohodnoceny celým číslem (integerem). V první iteraci algoritmus zváží pouze nejvyšší bit na každé hraně a vyřeší tento zjednodušený problém (ohodnocení hran jsou jednobitové). Ve druhé iteraci přidá další bit. Za pomoci výsledků z předchozí fáze vyřeší zjednodušený problém, kde u každé hrany zvažuje pouze 2 nejvyšší bity. V každé další iteraci přidá další bit z ohodnocení na hranách, až se nakonec dostane ke všem bitům a tím spočítá řešení původní úlohy.Dostaneme orientovaný graf $G=(V,E)$ s nezáporným ohodnocením hran $w(e)$. Chceme najít délky nejkratších cest z počátečního vrcholu $s$ do všech ostatních vrcholů $v$. Nechť $W$ označuje největší hodnotu, kterou je ohodnocena nějaká hrana. Chceme vymyslet algoritmus, který bude pracovat v čase $\OO(|E|\cdot \log W)$.

    Algoritmus začne s grafem $G$, který má hrany ohodnoceny pouze nejvyšším bitem z původních ohodnocení. Postupně v dalších iteracích přidává další bity. Konkrétně, nechť $k := \lceil \log (W+1) \rceil$ je počet bitů v binární reprezentaci každé hodnoty na hraně. V každé iteraci pro $i=1,2,\dots,k$ algoritmus uvažuje ohodnocení hran $w_i(e) := \lfloor w(e)/2^{k-i} \rfloor$ pro každou $e\in E$. Hodnota $w_i(e)$ je původní hodnota $w(e)$, která má snížené měřítko a obsahuje pouze nejvyšších $i$ bitů. Proto je $w_k(e)=w(e)$ pro každou hranu $e$. Například pokud $k=5$ a $w(e)=25$, což je v binární reprezentaci $[11001]_2$, tak $w_3(e)=[110]_2=6$.

    Definujme $\delta_i(u,v)$ jako délku nejkratší cesty z $u$ do $v$ v grafu $G$ s ohodnocením $w_i$. Délka nejkratší cesty v $G$ s ohodnocením $w$ $\delta(u,v)=\delta_k(u,v)$ pro všechny $u,v\in V$. Pro zadaný počáteční vrchol $s$ algoritmus nejprve spočítá $\delta_1(s,v)$ pro všechny $v\in V$. V dalších iteracích spočítá $\delta_2(s,v)$ pro všechny $v\in
    V$, dále $\delta_3(s,v)$ pro všechny $v\in V$,…, až se v poslední iteraci spočte $\delta_k(s,v)$ pro všechny $v\in V$. Celou dobu budeme předpokládat, že $|E|\geq |V|-1$. Pokud bude výpočet $\delta_i$ z $\delta_{i-1}$ trvat čas $\OO(|E|)$, tak celý algoritmus poběží v čase $\OO(|E|\cdot \log W)$.

    Nyní si odvodíte, proč a jak algoritmus funguje. Pomohou vám úkoly a nápovědy v následujích bodech.

    1. Předpokládejte, že $\delta(s,v) \leq |E|$ pro všechny $v\in V$. Ukažte, jak se dá spočítat $\delta(s,v)$ pro všechny $v\in V$ v čase $\OO(|E|)$. 
    2. Ukažte, jak spočítat $\delta_1(s,v)$ pro všechny $v\in V$ v čase $\OO(|E|)$. Tato iterace odpovídá hledání nejkratších cest v grafu bez ohodnocení hran.

      Nyní se zaměříme na výpočet $\delta_i$ z $\delta_{i-1}$.

    3. Dokažte, že pro $i=1,2,\dots, k$, buď $w_i(e)=2w_{i-1}(e)$ nebo $w_i(e)=2w_{i-1}(e)+1$. Potom dokažte, že pro všechna $v\in V$ $$ 2\delta_{i-1}(s,v) \leq \delta_i(s,v) \leq 2\delta_{i-1}(s,v) + |V|-1.$$
    4. Pro všechna $i=2,3,\dots, k$ a všechny hrany $uv\in E$ definujme $$ \widehat{w}_i(uv) = w_i(uv) + 2\delta_{i-1}(s,u) – 2 \delta_{i-1}(s,v).$$ Všiměte si, jak je nové ohodnocení hran podobné úpravě ohodnocení podle přípustného potenciálu (viz sekce [ref]min_cesta_potencial[/ref]).Pro všechna $i=2,3,\dots, k$ a všechny hrany $uv\in E$ dokažte, že upravená hodnota hrany $ \widehat{w}_i(uv)$ je celočíselná a nezáporná.
    5. Teď definujme $\widehat{\delta}_i(s,v)$ jako délku nejkratší cesty z $s$ do $v$ v grafu $G$ s ohodnocením $\widehat{w}_i$. Pro všechna $i=2,3,\dots, k$ a všechny hrany $uv\in E$ dokažte, že $$\delta_i(s,v) = \widehat{\delta}_i(s,v) + 2 \delta_{i-1}(s,v).$$ Na základě toho dokažte, že $\widehat{\delta}_i(s,v)\leq |V|-1 \le |E|$.
    6. Nyní konečně ukažte, jak spočítat $\delta_i(s,v)$ z hodnoty $\delta_{i-1}(s,v)$ pro všechny $v\in V$ v čase $\OO(|E|)$. Z toho vyvoďte, jak spočítat $\delta(s,v)$ pro všechny $v\in V$ v čase $\OO(|E|\log W)$.

Úlohy na úpravu grafu

Následující úlohy můžeme snadno převést na obyčejný problém hledání nejkratší cesty. Stačí vhodně upravit graf a ohodnocení hran.

  1. (Doprava v Absurdistánu)
    V Absurdistánu měli $N$ měst spojených navzájem leteckými linkami $S$ různých dopravních společností. Ale jak již to v tomto státě bývá, byrokracie se rozmohla a tak každá dopravní společnost měla různé tarify za překlad nákladu z letadel různých jiných společností. Přinesli Vám následující tabulky: 

    • $p(s,i,j)$ – cena účtovaná společností $s$ za přepravu vašeho nákladu z města $i$ do města $j$. Nekonečno, pokud taková letecká linka neexistuje.
    • $m(i,r,s)$ – cena účtovaná za přeložení nákladu z letadla společnosti $r$ do letadla společnosti $s$ v městě $i$. Nekonečno, pokud tomu úřední předpisy brání.

    Máte vyřešit, jak svůj náklad co nejlevněji přepravit z města $1$ do města $N$.

  2. (Nejkratší cesta mezi množinami $A$ a $B$)
    Dostaneme orientovaný graf $G=(V,E)$, ohodnocení $c\in \RR^m$ a dvě disjunktní množiny $A, B \subseteq V$. Najděte nejkratší cestu, která začíná ve vrcholu množiny $A$ a končí ve vrcholu množiny $B$. 

    Nápověda: Zkuste problém převést na běžný problém nejkratší cesty.

  3. (Nejkratší cesta s lichým počtem hran)
    Dostanete orientovaný graf s nezáporným ohodnocením hran. Chceme najít nejkratší cestu z vrcholu $s$ do $t$, která obsahuje lichý počet hran. Až to vyřešíte, tak si rozmyslete, co by se změnilo, kdybychom chtěli najít nejkratší cestu obsahující sudý počet hran? 

    Nápověda: nahraďte každý vrchol kromě $s$ a $t$ dvojicí vrcholů.

  4. (Zobecněný problém nejkratší cesty)
    Při internetovém routování dochází k prodlevám na jednotlivých linkách, ale také v samotných routrech. To nás motivuje k zobecnění problému nejkratší cesty. 

    Kromě cen na hranách (ohodnocení hran) máme i ceny ve vrcholech (ohodnocení vrcholů). Délka cesty v tomto novém modelu bude součet cen na hranách cesty plus součet cen ve vrcholech cesty (včetně koncových vrcholů).

    Dostanete orientovaný graf $G=(V,E)$ s kladným ohodnocením hran $c(e)$ a kladným ohodnocením vrcholů $c(v)$. Dále dostanete počáteční vrchol $s\in V$. Navrhněte efektivní algoritmus, který pro všechny vrcholy $v\in V$ vypíše cenu nejlevnější cesty z $s$ do $v$.

    Poznámka: Cena nejlevnější cesty z $s$ do $s$ je $c(s)$.

Ostatní úlohy

  1. (Počet nejkratších cest)
    Dostaneme neorientovaný neohodnocený graf a dva jeho vrcholy $u$, $v$. Mezi vrcholy $u$ a $v$ může existovat i více nejkratších cest. Navrhněte lineární algoritmus, který vypíše počet nejkratších cest mezi $u$ a $v$. 
  2. (Jednoznačnost nejkratší cesty)
    Dostanete orientovaný graf s kladným ohodnocením hran a počáteční vrchol $s$. Potřebovali bychom vyplnit boolovské pole $\ARRAY{unique}{\cdot}$, kde $\ARRAY{unique}{w} = {\tt true}$ právě tehdy když je nejkratší cesta z $s$ do $w$ jednoznačná (unikátní). 
  3. (Ověření korektnosti řešení) Dostanete orientovaný graf $G=(V,E)$, ohodnocení jeho hran $c$ (může být i záporné), počáteční vrchol $s$ a strom $T$, o kterém Vám někdo tvrdí, že je stromem nejkratší cesty. Navrhněte algoritmus, který ověří, že strom $T$ je opravdu stromem nejkratší cesty pro graf $G$ s ohodnocením $c$ a počátečním vrcholem $s$. Váš algoritmus by měl běžet v lineárním čase.
  4. (Hledání čtverců)
    Navrhněte algoritmus, který dostane neorientovaný graf a rozhodne, jestli graf obsahuje kružnici délky čtyři (čtverec). Časová složitost Vašeho algoritmu by neměla překročit $\OO(n^3)$. 
  5. (Algoritmus na délku nejkratší kružnice)
    Podívejte se na návrh algoritmu, který najde délku nejkratší kružnice v grafu bez ohodnocení hran. 

    Graf budeme procházet pomocí průchodu do hloubky (DFS). Každá zpětná hrana $uv$, na kterou narazíme, musí spolu se stromovými hranami vedoucími z $v$ do $u$ tvořit kružnici. Délka této kružnice je $level(u)-level(v)+1$, kde $level(w)$ je vzdálenost vrcholu $w$ od kořene ve stromě průchodu do hloubky. Tohle pozorování nás přivádí k následujícímu algoritmu. Budeme graf procházet do hloubky a u každého vrcholu si budeme pamatovat jeho $level$. Vždy když narazíme na zpětnou hranu, tak si spočítáme délku kružnice a porovnáme ji s dosud nejmenší nalezenou délkou kružnice.

    Ukažte, že tento algoritmus nemusí vždy fungovat. Nalezněte protipříklad a vysvětlete, proč je protipříkladem.

  6. (Délka nejkratšího cyklu)
    1. Dostanete obyčejný graf bez ohodnocení hran. Nalezněte algoritmus, který najde délku nejkratší kružnice v grafu nebo odpoví, že graf žádnou kružnici neobsahuje. Vaše řešení by mělo běžet v čase nejvýše $\OO(nm)$.
    2. Dostanete orientovaný graf s kladným ohodnocením hran. Nalezněte algoritmus, který spočítá délku nejkratšího cyklu. Pokud je graf acyklický, tak by to měl algoritmus zjistit. Vaše řešení by mělo běžet v čase nejvýše $\OO(n^3)$.
  7. (Délka nejkratšího cyklu obsahujícího hranu $e$)
    Dostanete neorientovaný graf $G=(V,E)$ s délkami hran $\ell_e$ pro každou hranu $e\in E$. Dále dostanete jednu konkrétní hranu $f\in E$. Najděte v čase $\OO(n^2)$ nejkratší kružnici obsahující hranu $f$. 
  8. (Hledání nejzápornějšího cyklu)
    Dostanete graf jehož hrany jsou ohodnoceny reálnými čísly, a to i zápornými. Najděte v tomto grafu záporný cyklus s co nejmenší hodnotou. 
  9. (Arbitráž)
    Proč hledat záporné cykly? Odpověď je jednoduchá. Abychom vydělali. Na světě funguje spousta směnáren. Kurz jedné měny vůči měně druhé nám říká, kolik jednotek jedné měny dostaneme za měnu druhou. Například kurz $k_{Eur/Kc}$ udává, kolik Euro dostaneme za 1 korunu (kurzy jsou znormované). Pokud chceme vyměnit koruny za Eura a pak na výletě v Německu Eura za Dolary, tak se kurzy násobí. Počet dolarů, které dostaneme výměnou za $100$\,Kč, spočítáme jako $k_{\$/Eur}\cdot k_{Eur/Kc}\cdot 100$. Předpokládáme, že výměna ve směnárnách probíhá bez poplatků. Nakonec si můžeme v Americe vyměnit dolary zpátky na české koruny. Množství korun, které tak získáme, záleží na kurzech měn. 

    Jak provádět výměny v jednotlivých směnárnách, abychom vydělali? Pokud je součin kurzů podél cyklické výměny číslo větší než jedna, tak vyděláme. Pokud je to číslo menší než jedna, tak naopak proděláme. Různé světové měny si můžete představit jako vrcholy grafu a kurzy měn jako ohodnocení hran. Navrhněte co nejrychlejší algoritmus, který v tomto grafu najde cykly, podél kterých se vyplatí vyměňovat peníze tak, abychom vydělali. Nápověda: Stačí převést násobení hodnot na hranách cesty na jejich sčítání. Toho docílíme tak, že si vytvoříme kopii grafu, ve které hrany ohodnotíme mínus logaritmem původního ohodnocení. V novém grafu budeme hledat záporné cykly. Proč při záporném cyklu vyděláme a při kladném ne?

  10. (Nejkratší cesty vedoucí přes vrchol $v_0$)
    Dostanete silně souvislý orientovaný graf $G=(V,E)$ s kladným ohodnocením hran. Graf je silně souvislý právě tehdy když z každého vrcholu existuje orientovaná cesta do libovolného jiného vrcholu. Dále dostanete jeden vrchol $v_0\in V$. Navrhněte efektivní algoritmus, který najde nejkratší cesty mezi každou dvojicí vrcholů, ale s tou podmínkou, že každá cesta musí procházet přes vrchol $v_0$. 
  11. (Přidání hrany, která nejvíce zkrátí nejkratší cesty)
    Je dána silniční síť $G=(V,E)$ propojující města $V.$ Pro každou silnici $e\in E$ známe její délku $\ell_e$. Ministerstvo dopravy chce rozšířit silniční síť o jednu novou silnici. Zatím má dlouhý seznam dvojic měst $E’$, které jsou kandidáty na propojení. Každá potenciální silnice $e’\in E’$ už je vyprojektovaná a víme, že bude mít délku $\ell_{e‘}$. Vás poprosili, abyste jim pomohli vybrat tu nejvhodnější z uvažovaných silnic. Ministři nejčastěji jezdí z města $s$ do města $t$ a proto Vám položili následují otázku: Stavba které silnice povede k největšímu snížení vzdálenosti mezi městy $s$ a $t$? Navrhněte efektivní algoritmus pro řešení této otázky.