Please enable JavaScript.

Coggle requires JavaScript to display documents.

10. Grafové problémy (Ohodnocené grafy ((G, w) (reálná funkce w: E(G) -…

- - - - pokud neexistuje cyklus záporné délky
- - - - pole d - nejkratší vzdál. z s do v
        
        počátek - d[s] = 0... poč. vrchol, d[s] = nek. ... ostatní
        
        na konci délky nejkratších vvzdáleností
      - pole p
        
        pole předchůdců vrcholu v
        
        počátek - null
        
        konec - nejkratší cesta je posl. vrcholů s, p[...p[v]...],...p[p[v]], p[v], v
      - počáteční vrchol s
      - pro každý vrchol udržujeme d[v], p[v]
      - vrcholy ve 2 disj. množinách
        
        S - zpracovávané - v d[v] je defin. nejkratší cesta z s do v
        
        Q - ostatní - v prioritní frontě, nejvyšší prior. - vrchol s nejnižší vzdál. od zprac. části
      - alg.
        
        odstraň u z počátku fronty
        
        přesuň u z Q do S
        
        projdi všechny doposud nezprac. potomky vi, přidej do pr. fronty
        
        relaxuj všechny hrany (u, v) - pokud d[v] > d[u] + w(u, v), uprav d[v] a p[v]
        
        po průchodu přes všechny potomky opakuj 1.
        
        konec: prior. fronta prázdná
    - - inicializace - lin. čas vzhledem k n
      - každá hrana 1/2* (neor. gr.)
      - slož. výběru z fronty dle impl.
        
        pole, seznam vrcholů - O(|V|^2 + |E|)
        
        binární halda - O(|V| + |E|) * log(|V|)
        
        Fibonacciho halda - O(|E| + |V| * log(|V|))
      - hlavní cyklus n-krát
  - - - začátek - d[s] = 0 (poč. vrchol), d[v] = nek. (ostatní)
      - konec - v d jsou nejkratší vzdál.
      - začátek - pole d - nejkratší vzdál. z s do v
      - max. n-1 iterací
      - pokud po n-1 projitích spustíme znovu a hodnoty v tab. se změní --> cyklus záporné délky --> fail
      - v každé iteraci projde všechny vrcholy a pokusí se najít nejkr. cestu z kořene --> do tabulky
    - - O(|V| * |E|)
- - - - vyžaduje, aby měly hrany unik. váhy --> nevznikají cykly
      - v každé fázi se počet komp. souv. sníží min. 2*
      - začátek - všechny uzly jsou samostatné komponenty
      - v každém kroku propojí každou komp. s jinou komp. pomocé nejkratší hrany
      - konec v log2(n) krocích
    - - O(|E| * log|V|)
  - - - vytvoř množinu S - obsahuje všechny hrany grafu
      - dokud je S neprázdná
        
        iia. pokud spojuje 2 různé podstromy, přidej ji do F... sluč podstromy
        
        iib. jinak hranu zahoď
        
        i. z S odeber hranu s min. váhou
      - vytvoř les F - každý uzel je samostatný podstrom
    - - vhodné dat. struktury - O(E * log(V))
  - - - inicializace: V' = {x}, kde x je lib. vrchol z V, E' = {}
      - opakuj, dokud není V' = V
        
        i. vyber hranu (u, v) z G s min. cenou - u je v V' a v není ve V'
        
        ii. přidej v do V', přidej (u, v) do E'
      - vstup: souvislý ohodnocený graf G(V, E)
      - výstup: G(V', E') - min. kostra
    - - matice sousednosti - O(V^2)
      - binární halda - O(E*log(V))
      - závisí na dat. struktuře ukládající okrajové hrany
      - Fibonacciho halda - O(E + V*log(V))