Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafy (Najkratšie cesty (Cesta
postupnosť vrcholov
najkratšia cesta sa…
Grafy
Najkratšie cesty
Cesta
- postupnosť vrcholov
- najkratšia cesta sa skladá z najkratších ciest
Dosiahnuteľnosť
- môžem sa dostať z vrcholu A do B
-
Algoritmy - SSSP
je tvorena predchodcami, ktory vyhovuju pre cestu, ohodnotenie hrán
Orientovaný graf
-
-
Ohodnotený
Nezáporný - Dijkstra (Pole - V^2, Binarna halda - V log V + E log V)
Záporný - Bellman-Ford (V*E)
zastavuje sa po V - 1 hranach pretoze jednoducha cesta ma v najhorsom pripade V - 1 hran
-
-
Relaxacia
- aktualizacia najkratšej cesty
Prieskum
Do šírky - BFS
hledání nejkratší cesty nebo
testování, zdali je graf bipartitní
Do hĺbky - DFS
hledání cyklů, nalezení
topologického uspořádání, rozdělení grafu na silně souvislé komponenty
-