hledat
Rozdíly
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 | ||
|
mgr-szz:in-pds:1-pds [2019/06/15 12:12] lachmanfrantisek |
mgr-szz:in-pds:1-pds [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řá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 * \log n)</math> | nezáporné délky hran | | + | | Dijkstrův algoritmus | <math>\mathcal{O}(m + n * \log n)</math> | nezáporné délky hran | |
| | Bellman-Ford | <math>\mathcal{O}(m * n)</math>| | | | 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 157: | Řádek 160: | ||
| * inicializace O(n), naplnění Q O(n), zpracování všech vrcholů O(n), relaxace všech hran O(m) + aktualizace hodnot v Q O(log n) pro každou hranu | * inicializace O(n), naplnění Q O(n), zpracování všech vrcholů O(n), relaxace všech hran O(m) + aktualizace hodnot v Q O(log n) pro každou hranu | ||
| * uvažujeme binární haldu, kde vložení je v průměru v O(1), odstranění minima O(log n) a aktualizace O(log n) | * uvažujeme binární haldu, kde vložení je v průměru v O(1), odstranění minima O(log n) a aktualizace O(log n) | ||
| - | * = O(m * log n) | + | * = O(m * log n) |
| + | * s využitím fibonacciho haldy: O(m + n * log n) | ||
| **Korektnost** | **Korektnost** | ||
| Řádek 177: | Řádek 181: | ||
| * 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> | ||
