Информатика / Алгоритмы и анализ данных

Алгоритм Дейкстры: релаксация и кратчайшие расстояния

Алгоритм Дейкстры находит кратчайшие пути от одной вершины при неотрицательных весах рёбер. На каждом шаге окончательно выбирается ещё не выбранная вершина с минимальной текущей меткой.

Опубликовано: 20 октября 2026 г.Обновлено: 20 октября 2026 г.

Формула

d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr),\qquad w(u,v)\geq0

Схема Дейкстра: расстояние от A

Выбранный путь A → C → B → D: сумма 4

Обозначения

$d(u),d(v)$: текущие оценки расстояния от старта, единица веса
$w(u,v)$: вес разрешённого перехода u → v, единица веса
$u,v$: вершины графа, идентификатор
$s$: источник с начальной меткой ноль, идентификатор

Условия применения

Все веса рассматриваемой модели неотрицательны и складываются в одной единице. Изначально только источник имеет метку ноль, остальные — бесконечность. В классической версии выбранная минимальная вершина окончательно фиксируется и больше не переоткрывается.

Ограничения

Окончательная фиксация минимальной метки не гарантирует правильности при отрицательных рёбрах. Остановка при первом обнаружении цели преждевременна: нужно дождаться выбора цели как минимальной вершины. Вес маршрута должен соответствовать исходной модели, а не меняться во время обхода.

Подробное объяснение

Метка d(v) описывает лучший уже найденный маршрут, но до выбора вершины ещё может уменьшаться. Релаксация проверяет, улучшит ли известный путь до u с добавленным ребром u→v текущую метку v. Если улучшит, сохраняются новая сумма и предшественник.

Главная операция — выбрать наименьшую метку среди незафиксированных вершин. При неотрицательных рёбрах обход через любую более далёкую невыбранную вершину не сможет уменьшить эту метку: к уже не меньшей стоимости добавляется неотрицательная сумма. Поэтому выбранное расстояние становится окончательным.

Это рассуждение объясняет и ограничение знака весов. Отрицательное ребро из позже выбранной вершины способно дать более дешёвый путь назад к уже зафиксированной. Нельзя просто проигнорировать знак или прибавить ко всем рёбрам одинаковую константу: пути содержат разное число рёбер.

При списках смежности и двоичной куче обычная реализация занимает O((V+E) log V). В варианте с повторными записями в куче устаревшие извлечённые метки пропускают. При простой линейной процедуре выбора вершины время составляет O(V²+E).

Кратчайший маршрут восстанавливают по предшественникам. Если нужна только одна цель, допустимо закончить при её окончательном выборе, но не при первом появлении в куче. Для недостижимой цели конечная метка не появляется: это отдельный результат, а не ошибка арифметики.

Как пользоваться формулой

Задайте старту ноль, прочим вершинам бесконечность и проверьте отсутствие отрицательных весов до начала обхода.
Выберите незавершённую вершину с минимальной меткой; при куче сначала отбросьте записи с устаревшими расстояниями.
Для каждого исходящего ребра сравните старую метку соседа с суммой d(u)+w; при улучшении обновите и предшественника.
Продолжайте до исчерпания достижимых вершин либо окончательного выбора цели; восстановите путь и проверьте сумму весов.

Историческая справка

Эдсгер Дейкстра опубликовал статью A note on two problems in connexion with graphs в 1959 году в журнале Numerische Mathematik. В ней рассматривались две разные сетевые задачи: минимальное дерево и кратчайший путь. Для пути важна последовательная фиксация ближайшей вершины, а не выбор самых дешёвых рёбер во всём графе. Современная запись через релаксацию и очередь с приоритетом делает этот принцип удобным для реализации и анализа сложности. При этом структура данных — отдельный уровень алгоритма: простой выбор минимума и двоичная куча приводят к разным затратам времени, сохраняя основную идею. Университетский каталог TU Eindhoven подтверждает публикацию 1959 года, а учебные материалы Princeton описывают неотрицательность весов и программную работу с метками.

Историческая линия формулы

Название связано с Эдсгером Дейкстрой и его публикацией 1959 года. Здесь рассматривается стандартная версия с окончательным выбором минимальной метки при неотрицательных весах; варианты с переоткрытием вершин и современные структуры приоритетов не смешиваются с исходным правилом.

Пример

Даны дуги A→B весом 4, A→C весом 1, C→B весом 2, C→D весом 5 и B→D весом 1. Веса — условные единицы стоимости. Из A метки B = 4 и C = 1. Выбираем C: путь через него уменьшает B до 1+2 = 3, а D получает 1+5 = 6. Далее выбираем B и улучшаем D до 3+1 = 4. Окончательный выбор D подтверждает расстояние 4. Предшественники дают A→C→B→D, сумма 1+2+1 = 4. Прямой маршрут A→B→D имеет стоимость 5, а A→C→D — 6. Проверка всех путей данного ациклического графа подтверждает минимум. Первое обнаружение D с меткой 6 ещё не позволяло завершить расчёт: эта метка была лишь временной.

Частая ошибка

Не фиксируйте цель при первом обнаружении. Не используйте классический алгоритм с отрицательными весами. Не прибавляйте константу ко всем рёбрам ради устранения отрицательных значений. Не обрабатывайте устаревшую запись кучи как новый верный путь. Не путайте кратчайшую сумму весов с минимальным числом рёбер.

Практика

Задачи с решением

Временная метка цели

Условие. Есть дуги S→T весом 9, S→A весом 2, A→T весом 3. Найдите расстояние S→T.

Решение. После S цель имеет 9, но A выбирается раньше с меткой 2. Релаксация A→T уменьшает цель до 2+3 = 5. Затем T фиксируется.

Ответ. 5 единиц через A.

Нулевой вес

Условие. Даны S→A весом 0, A→B весом 0 и S→B весом 2. Найдите расстояние S→B.

Решение. Неотрицательность допускает ноль. После выбора A сумма 0+0 уменьшает метку B с 2 до 0. Два перехода могут оказаться дешевле одного.

Ответ. 0 единиц; путь S→A→B.

Дополнительные источники

https://algs4.cs.princeton.edu/44sp/index.php
https://research.tue.nl/en/publications/a-note-on-two-problems-in-connexion-with-graphs/
https://algs4.cs.princeton.edu/lectures/keynote/44ShortestPaths.pdf

Связанные формулы

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.

Информатика

Алгоритм Беллмана — Форда: путь с отрицательными весами

$d_k(v)=\min\left(d_{k-1}(v),\min_{(u,v)\in E}\{d_{k-1}(u)+w(u,v)\}\right)$

Алгоритм Беллмана — Форда уточняет расстояния последовательными проходами по рёбрам. Он допускает отрицательные веса и позволяет обнаружить отрицательный цикл, достижимый из выбранного источника.

Информатика

Алгоритм Флойда — Уоршелла: пути между всеми парами

$d_{ij}^{(k)}=\min\left(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right)$

Алгоритм Флойда — Уоршелла находит расстояния между всеми парами вершин, последовательно разрешая новые промежуточные вершины. Его основа — сравнение прямого известного маршрута с маршрутом через очередную вершину.

Информатика

Алгоритм Краскала: вес минимального остовного дерева

$T\in\underset{\text{остовные деревья }S}{\operatorname{arg\,min}}\sum_{e\in S}w(e),\qquad |T|=V-1$

Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.