This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
courses:algorithms_building_and_analysis:lectures [2024/05/01 19:19] kalishenko |
courses:algorithms_building_and_analysis:lectures [2024/05/11 23:09] (current) kalishenko |
||
---|---|---|---|
Line 38: | Line 38: | ||
- Оптимизация Штейна алгоритма Каргера | - Оптимизация Штейна алгоритма Каргера | ||
- | ==== Кратчайшие пути. A* и его расширения ==== | + | ==== Кратчайшие пути. A* ==== |
- Напоминание об алгоритмах поиска пути: | - Напоминание об алгоритмах поиска пути: | ||
- Поиск в ширину | - Поиск в ширину | ||
Line 64: | Line 64: | ||
==== Потоки в графах ==== | ==== Потоки в графах ==== | ||
+ | - Напоминание Форда-Фалкерсона | ||
+ | * Идея поиска пути в остаточной сети | ||
+ | * Обратные рёбра | ||
+ | * Сложность | ||
- Алгоритм Гольдберга (проталкивания предпотока): | - Алгоритм Гольдберга (проталкивания предпотока): | ||
* Идея push-relabel алгоритмов | * Идея push-relabel алгоритмов |