Алгоритмы и структуры данных 8. Кратчайшие пути на графах. BFS, Дейкстра

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 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 - Корректность