Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Hledání nejkratší cesty v grafu

Definice

Ohodnocení hran - váhová funkce je funkce, která každé (orientované) hraně přiřazuje její délku nebo cenu jejího projití. Definuje se jako . Délka (orientované) cesty v ohodnoceném grafu (grafu s váhovou funkcí) je potom .

Vzdálenost dvou vrcholů (váha nejkr. cesty z do ) je je cesta z do , pokud nějaká cesta z do existuje, jinak . Nejkratší cesta z do je taková, pro kterou .

Poznámka

Pro hledání nejkratší cesty v obecném grafu bez ohodnocení hran (tj. délka cesty je počet hran na ní) stačí prohledávání do šířky.

Algoritmus (Algoritmus kritické cesty (pro DAG))

Pro hledání nejkratší cesty do všech bodů z jednoho zdroje v orientovaném acyklickém grafu (DAG) používá topologické třídění, které je pro takovýto graf proveditelné; spolu se zpřesňováním horních odhadů vzdáleností vrcholů.

Mám daný startovací vrchol . Definuji jako horní odhad vzdálenosti a , tj. vždy pro lib. vrchol . Hodnoty před započetím výpočtu inicializuji na .

V algoritmu se provádí operace Relax, znamenající zpřesnění odhadu za použití cesty vedoucí z do , končící hranou - pokud má taková cesta nižší váhu než byl předchozí odhad , položím . Tato operace zachovává invariant .

    Relax (u, v) { //u = source, v = destination
    if (v.distance > u.distance + uv.weight) {
    v.distance := u.distance + uv.weight
    v.predecessor := u
    }
    }

    kritická cesta( V - vrcholy, E - hrany, s - startovací vrchol ){

    topologicky setřiď V;
    inicializace - nastav d(s,v) = nekonečno pro všechny vrcholy;
    foreach( vrchol v, v pořadí podle top. třídění ){
    proveď operaci Relax za použití cest
    vedoucích do v přes všechna možná u;
    }
    }

Výsledek dává nejkratší cesty díky topologickému setřídění grafu - pro nejkr. cestu z do platí a pokud mám a provedu Relax na podle , pak dostanu , z čehož se korektnost dá dokázat indukcí podle počtu hran na cestě.

Složitost algoritmu je , protože taková je složitost topologického třídění a zbytek algoritmu každou hranu i každý vrchol testuje právě 1x.

Algoritmus (Dijkstrův algoritmus)

Pracuje na libovolném orientovaném grafu s nezáporným ohodnocením hran.

    Dijkstra( V - vrcholy, E - hrany, s - startovací vrchol ){

    inicializace - nastav d(s,v) = nekonečno pro všechny vrcholy;
    S = prázdný; // množina "vyřízených" vrcholů
    Q = V;       // množina "nevyřízených" vrcholů

    while( Q není prázdná ){
    vyber u, vrchol s nejmenším d z množiny Q;
    vlož vrchol u do S;
    foreach( v, z u do v vede hrana )
    proveď operaci Relax pro v přes u;
    }
    }

Časová složitost při implementaci množin a pomocí haldy je: pro inicializaci ( vložení do haldy), celkem pro vybírání prvků s nejmenším , jedno provedení Relax při změně trvá (úprava haldy) a provede se max. -krát; tedy celkem ).

Algoritmus (Bellman-Ford)

Bellman-Fordův algoritmus lze použít nejobecněji, ale je nejpomalejší. Funguje na libovolném grafu (pokud najde cyklus, jehož celková váha je záporná, a tedy nejkratší cesty nemají smysl, vrací chybu).

    Bellman-Ford( V - vrcholy, E - hrany, s - startovací vrchol ){

    inicializace - nastav d(s,v) = nekonečno pro všechny vrcholy;
    d(s,s) = 0;

    // n-1 iterací, každá projde všechny hrany
    for( i = 1; i < |V|; ++i ) {
    foreach( hrana (u,v) z E )
    proveď operaci Relax pro v přes u;
    }

    // hledání záporného cyklu
    foreach( hrana (u,v) z E ){
    if ( d(v) > d(u) + w(u,v) ){
    chyba - záporný cyklus;
    return;
    }
    }
    }

Složitost algoritmu je . Vždy najde nejkratší cestu, protože v grafu bez záporných cyklů může mít cesta max. vrcholů. Důkaz nalezení záporného cyklu sporem, se sumou vah všech hran na něm (položím 0).

Poznámka (Nejkratší cesty pro všechny dvojice vrcholů)

Pro hledání nejkratších cest pro všechny dvojice vrcholů lze buď použít -krát běh některého z předchozích algoritmů, nebo Algoritmus násobení matic či Floyd-Warshallův algoritmus. Ty oba používají matice sousednosti a počítají matici vzdáleností .

První z nich postupuje indukcí podle počtu hran na nejkr. cestě, vyrábí matice pro hran na nejkratší cestě. je , pro výpočet kroku vždy vynásobí použitím zvláštního násobení, kde násobení hodnot je nahrazeno sčítáním a sčítání výběrem minima. Složitost je s využitím asociativity takto definovaného násobení .

Floyd-Warshallův algoritmus jde indukcí podle velikosti množiny vrcholů, povolených jako vnitřní vrcholy na cestách. Používá jako min. váhu cesty z do s vnitř. vrcholy z množiny . V iniciálním kroku je taky . Pro -tý krok je . Složitost je , navíc jeden krok je velice rychlý - celkově je algoritmus většinou rychlejší než Bellman-Fordův a pro záporné cykly se časem na diagonále objeví záp. číslo, proto je není třeba testovat předem.