Алгоритмы и структуры данных 8. Кратчайшие пути на графах. BFS, Дейкстра
Автор: Лекторий ФПМИ
Загружено: 2022-04-02
Просмотров: 3878
Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики
Лекция прочитана 24 марта 2022 года
Лектор: Степанов Илья Даниилович
Оператор: Жильцов Игорь
Монтаж: Жильцов Игорь
0:00 - Кратчайшие пути в графе
4:35 - BFS. Кратчайшие пути от вершины до остальных в невзвешенном графе
11:40 - Асимптотика
12:25 - Корректность алгоритма
25:20 - Подойдёт ли DFS?
26:06 - 0-k BFS
34:25 - Корректность (б/д)
37:24 - Асимптотика
39:26 - Двусторонний BFS. Поиск кратчайшего пути из S в T в невзвешенном графе
43:10 - Корректность
48:10 - Зачем двусторонний BFS, если есть обычный? Время работы
52:43 - Алгоритм Дейкстры. Кратчайшие пути от вершины до остальных во взвешенном графе. O(N^2)
59:45 - Оптимизация Дейкстры до O(M log N). Бинкуча
1:02:42 - Оптимизация Дейкстры до O(M + N log N). Фибоначчиева куча
1:05:38 - Корректность
1:16:15 - Двусторонний алгоритм Дейкстры
1:19:46 - Время работы
1:20:21 - Корректность
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
