Где применяется
1. Задача
Навигатор должен довезти тебя от дома до аэропорта. Одни дороги короткие, но забиты пробками. Другие длинные, но пустые. Число поворотов тебя не волнует. Нужен маршрут, который займёт меньше всего времени.
Число дорог здесь ничего не решает. Три быстрых участка трассы могут оказаться быстрее двух медленных городских улиц. У каждой связи есть вес, то есть цена: минуты, километры, задержка. Нужно найти наименьшую суммарную цену до каждого места, а число шагов не важно.
Та же задача встречается в компьютерной сети. У каждой линии своя измеренная задержка. Нужна наименьшая суммарная задержка от одного компьютера до всех остальных.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитdijkstra(6, [[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], [[4, 3], [5, 6]], [[5, 1]], []], 0)Ищем кратчайшее расстояние от вершины 0 до каждой вершины. Все расстояния сначала ∞, вершина 0 получает 0 и попадает в кучу.
Столбики: текущее расстояние от вершины 0 до каждой вершины. Столбик во всю высоту значит, что до вершины ещё не дошли.
Одна операция: одна проверка ребра или один шаг внутри кучи. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(V·E)O(E log V)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- самый дешёвый/короткий путь со взвешенными рёбрами
- неотрицательные веса рёбер
- минимальная суммарная стоимость до каждого узла
- задержка в сети / стоимость маршрута, а не число дорог
- взвешенный граф, кратчайшие пути из одного источника
Похоже, но не то
- Обход графа BFS / DFS (Graph BFS / DFS)
Очередь считает шаги и считает все рёбра одинаковыми. Куча умеет работать с настоящими весами.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
Куча это инструмент, на котором всё держится. Та страница про сам контейнер.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Закрывать ближайшую вершину это жадный выбор. Он верен, пока нет отрицательных весов.
- Топологическая сортировка (алгоритм Кана) (Topological sort (Kahn's algorithm))
В графе без циклов порядок ослабляет рёбра без всякой кучи. Так быстрее, и отрицательные веса допустимы.
V вершин и E рёбер дают O(E log V) с кучей. Отрицательные веса её ломают, там нужен Беллман-Форд.
На LeetCode
Задачи, где нужен самый дешёвый маршрут, а рёбра стоят по-разному и не меньше нуля. Дейкстра достаёт из мин-кучи ближайший незаконченный узел и делает релаксацию его рёбер.
Запусти dijkstra из урока от k, и ответ равен наибольшему расстоянию или минус 1, если какой-то узел остался с Infinity.
Перемножай вместо сложения и держи наибольшее значение, с макс-кучей вместо мин-кучи.
Каждая клетка это узел, а путь стоит столько, сколько его самый большой шаг, поэтому при релаксации бери max вместо суммы.
Храни список смежности в классе, добавляй в него рёбра и запускай Дейкстру на каждый запрос.