Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Grafy: Přehledy, opakování, pseuodokódy

Základem grafových algoritmů je BFS/DFS

http://kam.mff.cuni.cz/~kuba/ka/pruchod.pdf
http://ksp.mff.cuni.cz/study/cooks/cookbook-chapters/05-grafy.pdf

Z BFS/DFS se odvíjí topologické uspořádání a Dijkstrův algoritmus

http://ksp.mff.cuni.cz/study/cooks/cookbook-chapters/05-grafy.pdf
http://kam.mff.cuni.cz/~kuba/ka/pruchod.pdf
http://kam.mff.cuni.cz/~kuba/ka/min_cesta.pdf

Úloha nejkratších cest se řešívá také pomocí Floyd-Warshallova nebo Bellman-Fordova algoritmu

http://kam.mff.cuni.cz/~kuba/ka/min_cesta.pdf

Maximální tok v síti v případě Ford-Fulkersonova algoritmu je jen opakovanou aplikací BFS/DFS a použijeme jej take pro nalezení maximálního párování

http://ksp.mff.cuni.cz/study/cooks/cookbook-chapters/15-toky-v-sitich.pdf
http://kam.mff.cuni.cz/~kuba/ka/toky.pdf

Téměř samovysvětlující kód pro maximální tok

http://www.aduni.org/courses/algorithms/courseware/handouts/Reciation_09.html

Stable Marriages

Stable marriage

Maďarský algoritmus

Popis je tady.
Pomohou příklady:
Ukázka 1, ukázka 2.

Úlohy pro seminář 14.11. 2013

courses/a4b36acm1/2013_zs/seminar_08.txt · Last modified: 2018/10/03 03:51 (external edit)