Алгоритм Дейкстры с кучей
Жадно находите кратчайшие пути по рёбрам с неотрицательными весами
«Алгоритм Дейкстры с кучей» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Задача о кратчайших путях
Вам нужен самый дешёвый маршрут от одной вершины до всех остальных. Алгоритм Дейкстры решает эту задачу, если вес каждого ребра равен нулю или положителен.
Жадная идея
Алгоритм Дейкстры является жадным: он всегда разворачивает непосещённую вершину с наименьшим известным расстоянием, считая это расстояние окончательным.
Зачем нужна мин-куча
Чтобы быстро извлекать ближайшую вершину, нужна мин-куча. Она возвращает наименьшее расстояние за время log n вместо медленного последовательного просмотра.
import heapqНачните с расстояний
Установите для каждого расстояния значение бесконечность, а для исходной вершины — ноль. До недостигнутых вершин так и останется невозможно добраться, поэтому их расстояния навсегда будут равны бесконечности.
dist = [float('inf')] * n
dist[src] = 0Добавьте начальную вершину в кучу
Поместите исходную вершину в кортеж (расстояние, вершина). Если поставить расстояние первым, куча автоматически упорядочит записи по стоимости.
pq = [(0, src)]Извлекайте ближайшую вершину
На каждой итерации извлекайте наименьшую пару (d, u). Это d — кратчайшее расстояние до u, поэтому после извлечения обработка этой вершины завершена.
d, u = heapq.heappop(pq)Пропускайте устаревшие записи
В куче может находиться вершина со старым, большим расстоянием. Пропустите её, если d больше сохранённого расстояния.
if d > dist[u]:
continueВыполняйте релаксацию соседей
Релаксация означает попытку улучшить расстояние до соседней вершины: если путь через u дешевле, обновите её расстояние и добавьте вершину в кучу.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))Приём с отложенным удалением
Кучи Python не умеют обновлять ключ, поэтому Вы добавляете дубликаты и игнорируете устаревшие записи. Такой ленивый подход делает код коротким и быстрым.
Время работы
С двоичной кучей алгоритм Дейкстры работает за O((V + E) log V). Этого достаточно для графов с сотнями тысяч рёбер.
Следите за весами рёбер
Алгоритм Дейкстры не работает с отрицательными рёбрами, поскольку извлечённое расстояние может оказаться неокончательным. В таких случаях используйте алгоритм Беллмана — Форда.
Быстрая проверка
Вы извлекли (d, u), но d больше, чем dist[u]. Что следует сделать?
Повторение: алгоритм Дейкстры с кучей
Вы инициализируете расстояния, добавляете (dist, node), извлекаете ближайшую вершину, пропускаете устаревшие записи и выполняете релаксацию соседей. Так работает алгоритм Дейкстры за O((V+E) log V). 🚀
Часто задаваемые вопросы
Урок «Алгоритм Дейкстры с кучей» бесплатный?
Да — полный текст урока «Алгоритм Дейкстры с кучей» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Алгоритм Дейкстры с кучей»?
Жадно находите кратчайшие пути по рёбрам с неотрицательными весами Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Алгоритм Дейкстры с кучей»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Алгоритм Дейкстры с кучей
- 0-1 BFS с деком
- Беллман — Форд и отрицательные рёбра
- Алгоритм Флойда — Уоршелла для всех пар