Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze Následující verze Obě strany příští revize | ||
mgr-szz:in-pds:1-pds [2019/06/15 11:53] lachmanfrantisek |
mgr-szz:in-pds:1-pds [2019/06/15 15:01] lachmanfrantisek |
||
---|---|---|---|
Řádek 140: | Řádek 140: | ||
</box> | </box> | ||
- | ^ algoritmus ^ složitost ^ typ grafu ^ | + | ^ algoritmus (1-to-n)^ složitost ^ typ grafu ^ |
| BFS | <math>\mathcal{O}(m+n)</math> | vzdálenost = počet hran | | | BFS | <math>\mathcal{O}(m+n)</math> | vzdálenost = počet hran | | ||
- | | Dijkstrův algoritmus | <math>\mathcal{O}(m \times \log n)</math> | nezáporné délky hran | | + | | Dijkstrův algoritmus | <math>\mathcal{O}(m * \log n)</math> | nezáporné délky hran | |
+ | | Bellman-Ford | <math>\mathcal{O}(m * n)</math>| | | ||
+ | |||
+ | ^ algoritmus (n-to-n)^ složitost ^ typ grafu ^ | ||
| Násobení matic | <math>\mathcal{O}(n^3 * \log n)</math> | | | | Násobení matic | <math>\mathcal{O}(n^3 * \log n)</math> | | | ||
| Floyd-Warshall | <math>\mathcal{O}(n^3)</math> | | | | Floyd-Warshall | <math>\mathcal{O}(n^3)</math> | | | ||
| Johnson | <math>\mathcal{O}(n^2 * \log n + m * n)</math> | | | | Johnson | <math>\mathcal{O}(n^2 * \log n + m * n)</math> | | | ||
+ | == Hledání nejkratších cest z jednoho vrcholu do všech == | ||
<box 90% blue|Dijkstrův algoritmus> | <box 90% blue|Dijkstrův algoritmus> | ||
Řádek 176: | Řádek 180: | ||
* BF vrátí true, protože platí trojúhelníková nerovnost; (jinak) pokud obsahuje dosažitelný negativní cyklus, vrátí false | * BF vrátí true, protože platí trojúhelníková nerovnost; (jinak) pokud obsahuje dosažitelný negativní cyklus, vrátí false | ||
</box> | </box> | ||
+ | |||
+ | == Hledání nejkratších cest mezi všemi vrcholy == | ||
<box 90% blue|Násobení matic> | <box 90% blue|Násobení matic> | ||
Řádek 224: | Řádek 230: | ||
^ algoritmus ^ složitost ^ | ^ algoritmus ^ složitost ^ | ||
- | | Borůvka | <math>\mathcal{O}(m \times \log n)</math> | | + | | Borůvka | <math>\mathcal{O}(m * \log n)</math> | |
- | | Kruskal | <math>\mathcal{O}(m \times \log n)</math> | | + | | Kruskal | <math>\mathcal{O}(m * \log n)</math> | |
- | | Jarník |<math>\mathcal{O}(m \times |DECREASE-KEY| + n \times |EXTRACT-MIN|)</math>| | + | | Jarník |<math>\mathcal{O}(m * |DECREASE-KEY| + n * |EXTRACT-MIN|)</math>| |
- | | Fredman-Tarjan (Jarník + Fibonacciho halda) |<math>\mathcal{O}(m + n \times \log n)</math>| | + | | Fredman-Tarjan (Jarník + Fibonacciho halda) |<math>\mathcal{O}(m + n * \log n)</math>| |
- | | Fredman-Tarjan (limit velikosti haldy) | <math>\mathcal{O}(m \times \beta (m, n))</math> | | + | | Fredman-Tarjan (limit velikosti haldy) | <math>\mathcal{O}(m * \beta (m, n))</math> | |
- | | Gabow et al. (F-T + packeting) | <math>\mathcal{O}(m \times \log \beta (m, n))</math> | | + | | Gabow et al. (F-T + packeting) | <math>\mathcal{O}(m * \log \beta (m, n))</math> | |
<box 90% blue|Kruskal> | <box 90% blue|Kruskal> | ||
Řádek 281: | Řádek 287: | ||
* => nejvýš <math>\log n</math> fází | * => nejvýš <math>\log n</math> fází | ||
* každá fáze zabere <math>\mathcal{O}(m)</math> (musíme projít přes všechny hrany) | * každá fáze zabere <math>\mathcal{O}(m)</math> (musíme projít přes všechny hrany) | ||
- | * celkem: <math>\mathcal{O}(m \times \log n)</math> | + | * celkem: <math>\mathcal{O}(m * \log n)</math> |
</box> | </box> | ||
Řádek 325: | Řádek 331: | ||
^ algoritmus ^ složitost ^ | ^ algoritmus ^ složitost ^ | ||
- | | Ford-Fulkerson |<math>\mathcal{O}(nm \times C)</math> C -- nejvyšší kapacita| | + | | Ford-Fulkerson |<math>\mathcal{O}(nm * C)</math> C -- nejvyšší kapacita| |
| Edmonds-Karp (FF + shortest aug. path) | <math>\mathcal{O}(m^2n)</math>| | | Edmonds-Karp (FF + shortest aug. path) | <math>\mathcal{O}(m^2n)</math>| | ||
|Dinitz (saturate all s-t paths in <math>G_f</math>)|<math>\mathcal{O}(mn^2)</math>| | |Dinitz (saturate all s-t paths in <math>G_f</math>)|<math>\mathcal{O}(mn^2)</math>| |