Где применяется
1. Задача
В прошлом уроке алгоритм Дейкстры находил самый дешёвый маршрут по взвешенной карте. Каждый раз он доставал из min-кучи самый дешёвый узел, цена которого ещё не окончательна. Из-за кучи в его оценке времени появляется множитель log. Когда веса любые, без кучи не обойтись.
Но во многих реальных графах у ребра бывает всего две цены: 0 или 1. Пример из реального случая этого урока: дата-центр, где серверы стоят в стойках. Переход между серверами одной стойки считаем бесплатным (0), переход в другую стойку стоит 1. Нужно узнать, сколько переходов между стойками нужно, чтобы добраться до каждого сервера.
Когда веса только 0 и 1, кучу можно убрать. Ту же работу быстрее делает двусторонняя очередь, за O(V + E). Этот приём называют 0-1 BFS.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на кратчайший путь, где каждый ход стоит 0 или 1, например стены, которые можно сломать, или стрелки, которые можно поменять. Дек заменяет кучу, бесплатные ходы идут в начало, платные в конец, и всё за O(V + E).
Шаг на пустую клетку стоит 0, а на препятствие 1, так что это zeroOneShortest из урока на сетке.
Идти по стрелке клетки стоит 0, а в любую другую сторону 1.
Состояние это полоса и позиция, ход вперёд стоит 0, а прыжок вбок 1.