MFF Notebook > Algoritmy

Algoritmy

Procházení grafů, řazení, atd.

Grafové

Jarník-Prim

O( |U| log |U| + |H| log |U| )

Nalezení minimální kostry grafu. Berou se hrany sestupně podle jejch váhy a přidávají se do grafu, pokud v něm nevytvoří kružnici.

Borůvka–Kruskal

Nalezení minimální kostry grafu.

Deep-first search

O( |U| + |H| )

Procházení grafu od určitého uzlu. Nové nalezené uzly jsou vkládání do zásobníku, ze kterého se také berou další uzly k prozkoumání. Pokud se neprochází strom do hloubky, musí si algoritmus pamatoval již nalezené uzly.

Breadth-first search

O( |U| + |H| )

Procházení grafu od určitého uzlu. Nové nalezené uzly jsou vkládání do fronty, ze které se také berou další uzly k prozkoumání. Pokud se neprochází strom do šířky, musí si algoritmus pamatoval již nalezené uzly.

Dijkstra

O( |H| + |U| log |U| )

Nalezení nejkratších cest z jednoho uzlu do všech ostatních. Váhy hran musí být nezáporné.

Bellman–Ford

O( |U| |H| )

Nalezení nejkratších cest z jednoho uzlu do všech ostatních. Provádí relaxaci všech hran při procházení grafem z jednoho uzlu, které je prováděno |U| krát.

Floyd–Warshall

O( |U|3 )

Nalezení nejkratších cest ze všech uzlů do všech uzlů. Tři cykly v sobě. Pro každou dvojici uzlů zkusí relaxovat přes všechny uzly.

Johnson

O( |U| ( |H| + |U| log |U| ) )

Nalezení nejkratších cest ze všech uzlů do všech uzlů.

Creative Commons License