кратчайший путь

Статьи

GRA Алгоритм Поиск в ширину Обходит граф слоями и находит пути с наименьшим числом рёбер за O(V + E). O(V + E) 2 задачи 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 Алгоритм Поток наименьшей стоимости Поток с наименьшей суммарной ценой: круги отрицательной стоимости, кратчайшие пути с потенциалами, транспортная задача 1930 года. O(F · E log V) 2 задачи STR Алгоритм Diff Майерса Кратчайший сценарий удалений и вставок строк за O((N + M) · D): волны по числу правок. Так работает git diff. O((N + M) · D) 1 задача DP Алгоритм Seam carving Сужает фото, вырезая пиксельные швы наименьшей энергии; каждый шов — динамика по таблице. O(W·H) на шов, O(k·W·H) на k швов 2 задачи DP Алгоритм Алгоритм Витерби Самая правдоподобная цепочка скрытых состояний по шумным наблюдениям: улицы по GPS, участки генома, сообщение по битам. O(T · S²) 2 задачи DP Алгоритм Красивый перенос строк Жадный перенос против всего абзаца сразу: кратчайший путь по местам разрыва, как в TeX. O(n·L) 2 задачи

Задачи

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

Часто рядом

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