Задачник Базовый курс EN

На чём держится

взвешенный граф

Статьи

GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи GRA Алгоритм A* Дейкстра с подсказкой «сколько ещё до финиша»: волна тянется к цели, а путь остаётся кратчайшим. O((V + E) log V) 2 задачи GRA Алгоритм Двунаправленный поиск Две волны Дейкстры навстречу друг другу: где остановиться, сколько экономится и как подружить с A*. O((V + E) log V) 2 задачи GRA Алгоритм Алгоритм Беллмана — Форда Кратчайшие пути с отрицательными рёбрами и поиск отрицательного цикла: V раундов по всем рёбрам. O(V · E) 2 задачи GRA Алгоритм Алгоритм Флойда — Уоршелла Кратчайшие пути между всеми парами вершин за O(n³): динамика по разрешённым пересадкам. O(n³) 2 задачи GRA Алгоритм Алгоритм Джонсона Кратчайшие пути при отрицательных весах: потенциалы Беллмана — Форда, перевзвешивание и Дейкстра от каждой вершины. O(V·E + V·(V + E) log V) 2 задачи GRA Алгоритм Иерархии сжатия Предподсчёт навигаторов: сжимаем неважные перекрёстки в ярлыки и ищем путь двумя волнами вверх. O((V + E′) log V) 1 задача GRA Алгоритм Минимальное остовное дерево Самая дешёвая сеть, связывающая все вершины: Борувка, Краскал и Прим — три способа применить одну лемму. O(E log V) 2 задачи GRA Алгоритм Максимальный поток Наибольший поток из истока в сток и узкое место сети: Форд — Фалкерсон, Эдмондс — Карп, теорема о разрезе. O(V E²) 2 задачи GRA Алгоритм Минимальный разрез Самая дешёвая граница в графе: вырезает предмет на фотографии и находит слабое место сети. O(m n² |C|) 2 задачи GRA Алгоритм Венгерский алгоритм Кому какую работу при наименьшей общей цене: потенциалы, честные пары и увеличивающие пути за O(n³). O(n³) 2 задачи GRA Алгоритм Поток наименьшей стоимости Поток с наименьшей суммарной ценой: круги отрицательной стоимости, кратчайшие пути с потенциалами, транспортная задача 1930 года. O(F · E log V) 2 задачи

Задачи

Аэропорты открываются Заехать по пути Маршрут курьера Не больше k обменов Разъезд со стадиона Честная подсказка Выгодный круг обменов Запросы по ярусам Один бесплатный проезд План перевозок Пожарные части Самый короткий круг Слабое место сети Электромобиль в горах Запасной маршрут Таблица между станциями

Часто рядом

граф 10 классика 10 кратчайший путь 8 карты и навигация 8 куча 5 сети 5 собеседования 5 эвристика 3 олимпиады 3 потоки 3 логистика 3 оптимизация 3