Contest 18.4. 2013

Přehled, 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

courses/acm/2013_ls/seminar8.txt · Last modified: 2025/09/25 15:31 (external edit)