Алгоритм Дейкстры 🧭

Открой любой навигатор — Яндекс Карты, Google Maps, 2ГИС — и попроси построить маршрут из точки A в точку B. За долю секунды приложение переберёт десятки тысяч перекрёстков и дорог, каждая из которых «стоит» разное время проезда, и выдаст маршрут, который гарантированно быстрее любого другого. Это не магия и не полный перебор всех возможных путей — это конкретный алгоритм с именем, историей и доказанной математической корректностью. Именно ему посвящён этот урок.

В уроке 261 ты уже решал похожую на первый взгляд задачу — поиск кратчайшего пути через обход в ширину (BFS). Но там все рёбра графа были равноправны: переход по любому ребру стоил «один шаг», а кратчайший путь означал путь с минимальным числом рёбер. В реальном мире так почти никогда не бывает. Дорога через шоссе и дорога через двор — это оба ребра графа дорог, но по времени они совершенно не равны. Пакет данных, идущий через оптоволоконный кабель и через спутниковый канал, добирается до цели за разное время. Взвешенный граф — граф, где у каждого ребра есть число, отражающее его «стоимость» (время, расстояние, деньги, задержку), — требует принципиально другого инструмента, потому что BFS с подсчётом рёбер здесь попросту даёт неверный ответ: путь с меньшим числом рёбер может оказаться значительно длиннее по суммарному весу, чем путь с большим числом более коротких рёбер.

Здесь на сцену выходит алгоритм Дейкстры — один из самых цитируемых и самых практически используемых алгоритмов в истории информатики. Его область применения выходит далеко за пределы навигаторов и куда ближе к тому, чем ты как специалист по данным будешь заниматься каждый день. В рекомендательных системах, построенных на графах социальных связей, часто нужно найти кратчайшую цепочку знакомств между двумя пользователями («вы находитесь на расстоянии трёх рукопожатий») — это прямое применение алгоритма Дейкстры к графу дружбы, где вес ребра отражает, например, частоту взаимодействия. В сетевом анализе кратчайшие пути лежат в основе таких метрик центральности, как betweenness centrality, широко используемых для анализа влиятельности узлов в графах знаний и социальных сетях. В логистике, где ML-модели предсказывают время в пути на каждом участке маршрута с учётом пробок, погоды и исторических данных, эти предсказанные веса подаются на вход именно алгоритму Дейкстры, чтобы построить итоговый маршрут доставки. И, что не менее важно, алгоритм Дейкстры — это едва ли не самый чистый и самый доказуемый пример жадного алгоритма: конструкции, которая на каждом шаге принимает локально оптимальное решение и при этом, при выполнении определённых условий, гарантированно приходит к глобально оптимальному результату. Понимание того, почему это работает — и, что не менее важно, почему это перестаёт работать при малейшем нарушении условий, — один из самых ценных концептуальных уроков, которые можно вынести из курса алгоритмов.

В этом уроке ты разберёшь постановку задачи о кратчайшем пути от одной вершины до всех остальных, разберёшь жадную идею алгоритма Дейкстры и механизм релаксации рёбер на полной пошаговой трассировке конкретного графа, увидишь на конкретном контрпримере, почему алгоритм ломается при отрицательных весах рёбер, и изучишь, как переход от наивного линейного поиска минимума к приоритетной очереди (min-heap) ускоряет алгоритм с $O(V^2)$ до $O((V+E)\log V)$ — разницы, которая на графах с миллионами вершин означает разницу между секундами и часами работы.

История: как Дейкстра придумал алгоритм за двадцать минут в кафе

Эдсгер Вибе Дейкстра (Edsger Wybe Dijkstra) — нидерландский информатик, один из самых влиятельных людей в истории computer science, чьё имя носят сразу несколько фундаментальных алгоритмов и концепций (алгоритм Дейкстры, алгоритм банкира, флаг Дейкстры для трёхцветной сортировки, знаменитое эссе «Goto считается вредным»). В середине 1950-х годов он работал в Математическом центре в Амстердаме программистом на одной из первых в Нидерландах электронных вычислительных машин — ARMAC. Дейкстра занимался демонстрацией возможностей нового компьютера широкой публике и искал задачу, которая была бы одновременно достаточно простой, чтобы её понял человек без специального образования, и достаточно впечатляющей, чтобы показать реальную вычислительную мощь машины.

Идея пришла к нему в 1956 году, когда он с невестой Марией зашёл в кафе в Амстердаме отдохнуть после похода по магазинам. У него не было под рукой ни бумаги, ни карандаша — и именно это ограничение, по собственному признанию Дейкстры много лет спустя, заставило его искать максимально простое решение, которое можно было целиком удержать в голове. За примерно двадцать минут, сидя за столиком кафе, он придумал алгоритм поиска кратчайшего пути между двумя городами на упрощённой карте Нидерландов, с которой работал для демонстрации: изначально он выбрал всего 64 города, чтобы иллюстрация была наглядной и уместилась на экране показа. Дейкстра сам объяснял простоту алгоритма именно требованием обходиться без сложного математического аппарата — задача должна была быть понятна журналистам и широкой публике на демонстрации возможностей ARMAC.

Опубликовал он свой алгоритм далеко не сразу — только в 1959 году, в статье «A note on two problems in connexion with graphs» («Заметка о двух проблемах, связанных с графами»), которая заняла всего три страницы в журнале Numerische Mathematik. В этой короткой статье Дейкстра описал сразу два результата: собственно алгоритм поиска кратчайшего пути от одной вершины до всех остальных (тот, что разбирается в этом уроке) и алгоритм построения минимального остовного дерева, очень похожий на позже независимо переоткрытый и куда более известный алгоритм Прима. Показательно, что сам Дейкстра, по собственным более поздним воспоминаниям, не считал изобретение алгоритма чем-то из ряда вон выходящим в момент его появления — он воспринимал задачу скорее как удобный учебный пример для демонстрации возможностей компьютера, а не как отдельное научное достижение. Понадобились десятилетия, чтобы алгоритм, придуманный за двадцать минут без единой записи, стал одним из самых широко используемых алгоритмов в истории вычислительной техники — от маршрутизации интернет-трафика по протоколам вроде OSPF до навигационных систем, которыми пользуются миллиарды людей каждый день.

Постановка задачи: кратчайший путь во взвешенном графе

Интуиция

Представь граф городов, где рёбра — это дороги, а вес каждого ребра — время в пути в минутах. Задача звучит так: находясь в конкретном городе-источнике, найти кратчайшее по суммарному времени расстояние до каждого другого достижимого города. Это принципиально отличается от задачи, которую решал BFS в уроке 261: там «кратчайший» означало «наименьшее число рёбер», здесь «кратчайший» означает «наименьшая сумма весов рёбер вдоль пути» — и путь с большим числом рёбер вполне может оказаться короче по суммарному весу, чем путь с меньшим числом рёбер, но одним очень «дорогим» участком.

Важное ограничение, без которого классический алгоритм Дейкстры не работает корректно (к этому вопросу отдельно и подробно вернёмся чуть ниже): все веса рёбер должны быть неотрицательными. Отрицательный вес ребра интуитивно означал бы «переход, который не просто ничего не стоит, а ещё и приносит выгоду» — и, забегая вперёд, именно эта возможность разрушает жадную логику алгоритма.

Формальное определение

Определение. Дан взвешенный ориентированный граф $G=(V,E)$ с весовой функцией $w: E \to \mathbb{R}_{\ge 0}$, сопоставляющей каждому ребру неотрицательное число, и выделенная стартовая вершина $s \in V$ (источник). Задача о кратчайшем пути от одной вершины до всех остальных (single-source shortest path) состоит в том, чтобы для каждой вершины $v \in V$ найти величину

$$d(s, v) = \min_{\text{путь } p \text{ от } s \text{ до } v} \sum_{e \in p} w(e),$$

то есть минимальную суммарную стоимость среди всех путей от $s$ до $v$ в графе; если $v$ недостижима из $s$, полагаем $d(s,v) = \infty$.

Обрати внимание на формулировку «до всех остальных», а не «до одной конкретной вершины» — это важная деталь. Алгоритм Дейкстры в классическом виде решает более общую задачу: он за один проход строит кратчайшие расстояния сразу до всех вершин графа, а не только до одной интересующей нас цели (хотя, как ты увидишь в разделе с практикой, алгоритм легко модифицировать для досрочной остановки, если нужна только одна целевая вершина).

Примеры с разбором

Пример 1. Граф городов с временем в пути. Пусть вершины графа — города A, B, C, D, а рёбра — прямые дороги: A→B (30 минут), A→C (100 минут), B→C (20 минут), C→D (10 минут). Путь от A до D напрямую через C стоил бы $100+10=110$ минут, но путь A→B→C→D стоит всего $30+20+10=60$ минут — почти вдвое быстрее, несмотря на то что состоит из трёх рёбер вместо двух. Задача алгоритма Дейкстры — автоматически найти этот более дешёвый, хотя и более «длинный по числу рёбер», путь.

Пример 2. Граф сети передачи данных. Вершины — маршрутизаторы, рёбра — сетевые соединения между ними, вес ребра — задержка передачи пакета в миллисекундах. Протоколы маршрутизации вроде OSPF (Open Shortest Path First), используемые внутри крупных сетей и интернет-провайдеров, в буквальном смысле реализуют алгоритм Дейкстры для построения таблиц маршрутизации: каждый маршрутизатор строит для себя дерево кратчайших путей до всех остальных узлов сети на основе весов соединений.

Пример 3. Граф социальной сети для рекомендаций. Вершины — пользователи, рёбра — связи (подписки, дружба), вес ребра — обратная величина от силы связи (чем чаще два пользователя взаимодействуют, тем меньше вес соответствующего ребра). Кратчайший путь от одного пользователя до другого в таком графе можно интерпретировать как «кратчайшую значимую цепочку связей» между ними — метрику, которую используют некоторые рекомендательные системы, чтобы объяснить, почему конкретный пользователь может быть интересен другому («у вас есть общий близкий контакт через двух посредников»).

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

Жадная идея и релаксация рёбер

Интуиция

Представь, что ты — курьер, который должен разнести посылки по всем адресам города, начиная с одной точки, и хочешь точно знать кратчайшее время до каждого адреса. Естественная жадная стратегия: сначала точно узнать кратчайшее время до самого близкого адреса (он же, очевидно, ближайший — до него нет более быстрого способа добраться, чем напрямую или через ещё более близкие точки, которых просто не существует). Как только это время «зафиксировано» как окончательное, можно пройтись по всем дорогам, отходящим от этого адреса, и посмотреть — не сокращают ли они путь до каких-то ещё не проверенных адресов. Обновив оценки, снова выбираешь следующий по близости адрес среди ещё не проверенных — и повторяешь процесс.

Это и есть жадная идея алгоритма Дейкстры: на каждом шаге среди ещё не «финализированных» (не посещённых) вершин выбирается та, у которой текущая оценка расстояния от источника минимальна, эта оценка объявляется окончательной, а все рёбра, исходящие из выбранной вершины, используются для попытки улучшить оценки соседних вершин. Такая попытка улучшения называется релаксацией ребра — по аналогии с натянутой струной или пружиной: если через ребро $(u,v)$ веса $w$ можно «ослабить» текущую оценку расстояния до $v$ (то есть уменьшить её), релаксация это делает; если улучшения нет, оценка остаётся как была.

Алгоритм

Алгоритм Дейкстры.

1. Инициализация: положить $d(s) = 0$ и $d(v) = \infty$ для всех остальных вершин $v$; все вершины считаются непосещёнными.
2. Пока среди непосещённых вершин есть хотя бы одна с конечной оценкой расстояния:
   • a. Выбрать непосещённую вершину $u$ с минимальным значением $d(u)$.
   • b. Пометить $u$ как посещённую — значение $d(u)$ теперь считается окончательным и больше не изменяется.
   • c. Для каждого ребра $(u, v)$ веса $w$, исходящего из $u$: выполнить релаксацию — если $d(u) + w < d(v)$, обновить $d(v) \leftarrow d(u) + w$.
3. Когда все достижимые вершины посещены, вернуть массив расстояний $d(v)$ для всех $v$.

Формула релаксации ребра $(u,v)$ веса $w$ в явном виде:

Это единственная операция, которая изменяет оценки расстояний на протяжении всего алгоритма — вся логика Дейкстры сводится к тому, в каком порядке и для каких вершин её применять.

Примеры с разбором

Пример 1. Релаксация на одном ребре. Пусть $d(A) = 0$ (источник), $d(B) = \infty$ (ещё не найден ни один путь), и есть ребро $A \to B$ веса $7$. Релаксация: $d(B) \leftarrow \min(\infty, 0+7) = 7$. Теперь пусть позже находится ещё один путь до $B$ — ребро $C \to B$ веса $2$, при этом $d(C) = 3$ уже зафиксировано как окончательное. Повторная релаксация того же ребра: $d(B) \leftarrow \min(7, 3+2) = \min(7, 5) = 5$ — оценка улучшилась, потому что через $C$ добраться до $B$ дешевле.

Пример 2. Небольшой граф для интуиции жадного выбора. Граф из трёх вершин: $A \to B$ веса $4$, $A \to C$ веса $1$, $C \to B$ веса $1$. Старт в $A$: $d(A)=0$, $d(B)=\infty$, $d(C)=\infty$. Инициализация даёт $d(B) = 4$, $d(C) = 1$ (прямые рёбра из $A$). Среди непосещённых минимальное значение у $C$ ($d(C)=1 < d(B)=4$), поэтому жадно выбираем и фиксируем $C$. Релаксация ребра $C \to B$: $d(B) \leftarrow \min(4, 1+1) = 2$. Только теперь выбираем и фиксируем $B$ с итоговым $d(B) = 2$ — путь $A \to C \to B$ оказался вдвое короче прямого ребра $A \to B$, и жадный алгоритм нашёл это автоматически, потому что не зафиксировал $B$ раньше времени.

Пример 3. Полная пошаговая трассировка на графе из шести вершин. Рассмотрим ориентированный взвешенный граф с вершинами $A, B, C, D, E, F$ и рёбрами:

A → B  (вес 4)
A → C  (вес 2)
C → B  (вес 1)
B → D  (вес 5)
C → D  (вес 8)
C → E  (вес 10)
D → E  (вес 2)
D → F  (вес 6)
E → F  (вес 3)

Стартовая вершина — $A$. Проследим все шаги алгоритма.

Инициализация. $d(A)=0$, $d(B)=d(C)=d(D)=d(E)=d(F)=\infty$. Непосещённые: $\{A,B,C,D,E,F\}$.

Шаг 1. Минимальная непосещённая вершина — $A$ ($d=0$). Фиксируем $A$. Релаксация рёбер из $A$: $A\to B$ даёт $d(B)\leftarrow\min(\infty,0+4)=4$; $A\to C$ даёт $d(C)\leftarrow\min(\infty,0+2)=2$. Текущие оценки: $d(A){=}0^*,\ d(B){=}4,\ d(C){=}2,\ d(D){=}\infty,\ d(E){=}\infty,\ d(F){=}\infty$ (звёздочкой отмечаем зафиксированные).

Шаг 2. Минимальная среди непосещённых — $C$ ($d=2$, меньше чем $d(B)=4$). Фиксируем $C$. Релаксация рёбер из $C$: $C\to B$ даёт $d(B)\leftarrow\min(4, 2+1)=3$ (улучшение!); $C\to D$ даёт $d(D)\leftarrow\min(\infty,2+8)=10$; $C\to E$ даёт $d(E)\leftarrow\min(\infty,2+10)=12$. Текущие оценки: $d(A){=}0^*,\ d(B){=}3,\ d(C){=}2^*,\ d(D){=}10,\ d(E){=}12,\ d(F){=}\infty$.

Шаг 3. Минимальная среди непосещённых — $B$ ($d=3$). Фиксируем $B$. Релаксация рёбер из $B$: $B\to D$ даёт $d(D)\leftarrow\min(10, 3+5)=8$ (улучшение!). Текущие оценки: $d(A){=}0^*,\ d(B){=}3^*,\ d(C){=}2^*,\ d(D){=}8,\ d(E){=}12,\ d(F){=}\infty$.

Шаг 4. Минимальная среди непосещённых — $D$ ($d=8$). Фиксируем $D$. Релаксация рёбер из $D$: $D\to E$ даёт $d(E)\leftarrow\min(12, 8+2)=10$ (улучшение!); $D\to F$ даёт $d(F)\leftarrow\min(\infty, 8+6)=14$. Текущие оценки: $d(A){=}0^*,\ d(B){=}3^*,\ d(C){=}2^*,\ d(D){=}8^*,\ d(E){=}10,\ d(F){=}14$.

Шаг 5. Минимальная среди непосещённых — $E$ ($d=10$). Фиксируем $E$. Релаксация ребра из $E$: $E\to F$ даёт $d(F)\leftarrow\min(14, 10+3)=13$ (улучшение!). Текущие оценки: $d(A){=}0^*,\ d(B){=}3^*,\ d(C){=}2^*,\ d(D){=}8^*,\ d(E){=}10^*,\ d(F){=}13$.

Шаг 6. Осталась одна непосещённая вершина — $F$ ($d=13$). Фиксируем $F$. У $F$ нет исходящих рёбер, релаксировать нечего. Все вершины посещены — алгоритм завершается.

Итоговый результат: $d(A)=0$, $d(B)=3$, $d(C)=2$, $d(D)=8$, $d(E)=10$, $d(F)=13$. Порядок фиксации вершин: $A, C, B, D, E, F$ — обрати внимание, что он не совпадает с алфавитным или с порядком «числа рёбер от старта» ($B$ достижима за одно ребро от $A$, но зафиксирована позже $C$, достижимой тоже за одно ребро, потому что вес ребра $A\to C$ меньше веса $A\to B$). Кратчайший путь до $F$ — не прямой (через $D\to F$, что дало бы $8+6=14$), а через $E$ ($D\to E\to F = 8+2+3=13$) — именно этот факт и находит релаксация на шаге 5.

Почему это важно. Пошаговая трассировка наглядно показывает главное свойство алгоритма: как только вершина зафиксирована (посещена), её расстояние больше никогда не меняется, и весь дальнейший процесс — это последовательное «расширение множества окончательно известных расстояний» на одну вершину за шаг, всегда выбирая следующей наиболее близкую к источнику из ещё неизвестных. Именно порядок выбора — всегда минимальная непосещённая оценка — гарантирует (при неотрицательных весах, о чём подробнее в следующем разделе), что зафиксированное значение действительно окончательно правильное, а не просто «пока лучшее найденное».

Почему алгоритм Дейкстры не работает с отрицательными весами

Интуиция

Вся корректность жадного выбора в алгоритме Дейкстры держится на одном скрытом предположении: если вершина $u$ имеет минимальную оценку расстояния среди всех непосещённых вершин, то никакой более длинный путь через другие вершины не сможет дать до неё путь ещё короче — потому что любой такой путь обязательно проходит через хотя бы одну ещё не посещённую вершину, а её текущая оценка расстояния уже не меньше $d(u)$, и добавление к ней ещё какого-то неотрицательного веса ребра только увеличит итоговую сумму. Это рассуждение полностью разваливается, если веса рёбер могут быть отрицательными: тогда путь может «удлиниться» по числу рёбер и по промежуточным оценкам, но в итоге стать короче за счёт отрицательного ребра в конце.

Контрпример

Рассмотрим ориентированный граф из трёх вершин $A, B, C$ с рёбрами $A \to B$ веса $1$, $A \to C$ веса $2$ и $C \to B$ веса $-2$. Настоящий (истинный) кратчайший путь от $A$ до $B$ — это путь $A \to C \to B$ с суммарным весом $2 + (-2) = 0$, что меньше, чем прямой путь $A \to B$ весом $1$.

Проследим, что делает классический алгоритм Дейкстры на этом графе. Инициализация: $d(A)=0$, $d(B)=d(C)=\infty$. Релаксация рёбер из $A$: $d(B)\leftarrow 0+1=1$, $d(C)\leftarrow 0+2=2$. Среди непосещённых минимальное значение — у $B$ ($d(B)=1 < d(C)=2$). Алгоритм жадно выбирает $B$ и фиксирует $d(B)=1$ как окончательное. Затем фиксируется $C$ с $d(C)=2$, релаксация ребра $C\to B$ даёт $2+(-2)=0$, что меньше текущего $d(B)=1$ — но $B$ уже помечена как посещённая, и по правилам классического алгоритма её значение больше не пересматривается.

Итог: алгоритм Дейкстры вернёт $d(B)=1$, тогда как истинное значение $d(B)=0$. Алгоритм ошибся именно потому, что зафиксировал $B$ раньше, чем узнал о более дешёвом пути через $C$ — а более дешёвый путь стал возможен только благодаря отрицательному весу ребра $C \to B$, которое «компенсировало» стоимость пути до $C$.

Разбор ошибки и альтернативы

Пример 2. Почему увеличение всех весов на константу не спасает ситуацию. Может показаться, что проблему легко решить: прибавить ко всем весам рёбер достаточно большую константу, чтобы избавиться от отрицательных значений, а потом просто вычесть эквивалент из итогового результата. Это не работает корректно, потому что константа прибавляется за каждое ребро на пути, а не один раз, — а значит, такое преобразование искажает относительную стоимость путей с разным числом рёбер: путь из пяти дешёвых рёбер после сдвига может стать «дороже» пути из двух дорогих рёбер, хотя до сдвига было наоборот. Единого сдвига, который сохраняет правильный порядок путей по стоимости, в общем случае не существует.

Пример 3. Правильное решение — алгоритм Беллмана-Форда. Для графов с отрицательными весами рёбер (но без циклов отрицательного суммарного веса, о которых отдельно ниже) существует алгоритм Беллмана-Форда — он расплачивается более высокой асимптотической сложностью $O(V\cdot E)$ вместо $O((V+E)\log V)$ у Дейкстры, но зато не полагается на жадную фиксацию вершин: вместо этого он последовательно релаксирует все рёбра графа $V-1$ раз подряд, гарантированно распространяя любое улучшение по всему графу, независимо от порядка. На графе из контрпримера выше алгоритм Беллмана-Форда корректно вернул бы $d(B)=0$.

Отдельный случай — отрицательный цикл. Если в графе существует цикл, суммарный вес рёбер которого отрицателен (например, $X\to Y$ весом $-3$ и $Y\to X$ весом $1$, суммарно $-2$ за проход по циклу), задача о кратчайшем пути вообще перестаёт быть корректно определена: проходя по такому циклу бесконечное число раз, можно уменьшать суммарную стоимость пути сколь угодно, кратчайшего пути в математическом смысле просто не существует ($d(v) \to -\infty$). Алгоритм Беллмана-Форда умеет обнаруживать такие циклы (если после $V-1$ итераций релаксация всё ещё что-то улучшает — значит, есть отрицательный цикл), а классический алгоритм Дейкстры такую ситуацию корректно обработать не способен в принципе.

Почему это важно. Понимание границ применимости алгоритма — не менее важный навык, чем понимание самого алгоритма. На собеседованиях и в реальной инженерной практике вопрос «а что если веса могут быть отрицательными?» — один из самых частых способов проверить, действительно ли человек понимает почему работает жадная стратегия, а не просто заучил последовательность шагов. В прикладных задачах отрицательные веса рёбер встречаются чаще, чем кажется: например, в финансовых графах арбитражных возможностей вес ребра может отражать логарифм обменного курса, который вполне может быть отрицательным, и поиск отрицательного цикла в таком графе — это в буквальном смысле поиск арбитражной возможности на валютном рынке.

Реализация через приоритетную очередь (min-heap)

Интуиция

В пошаговой трассировке выше на каждом шаге алгоритма требовалось найти непосещённую вершину с минимальной текущей оценкой расстояния. Самая наивная реализация — линейный перебор всех вершин на каждом шаге в поисках минимума — при $V$ вершинах и $V$ шагах алгоритма даёт $O(V^2)$ операций только на поиск минимумов, плюс $O(E)$ суммарно на все релаксации рёбер: итоговая сложность наивной версии — $O(V^2 + E)$. Для плотных графов, где $E$ близко к $V^2$, это приемлемо. Но для разреженных графов — а большинство реальных графов (дорожные сети, социальные графы, интернет-топология) именно такие, число рёбер там растёт примерно линейно с числом вершин, а не квадратично, — $O(V^2)$ становится непозволительно медленным.

Решение — заменить линейный поиск минимума структурой данных, специально предназначенной для быстрого извлечения минимального элемента: приоритетной очередью, реализованной как min-heap (минимальная двоичная куча). Куча позволяет добавить элемент и извлечь минимальный элемент каждый за $O(\log n)$ операций вместо $O(n)$ при линейном переборе — а именно эти две операции (добавление обновлённой оценки расстояния, извлечение вершины с минимальной оценкой) и составляют основной цикл алгоритма Дейкстры.

Алгоритм с приоритетной очередью

Алгоритм Дейкстры с min-heap.

1. Инициализировать $d(s)=0$, $d(v)=\infty$ для остальных вершин. Создать пустую приоритетную очередь и добавить в неё пару $(0, s)$.
2. Пока очередь не пуста:
   • a. Извлечь из очереди пару $(dist, u)$ с минимальным $dist$.
   • b. Если $u$ уже посещена (значит, эта запись в очереди устарела) — пропустить её и перейти к следующей итерации.
   • c. Пометить $u$ как посещённую.
   • d. Для каждого ребра $(u,v)$ веса $w$: если $d(u)+w < d(v)$, обновить $d(v) \leftarrow d(u)+w$ и добавить в очередь пару $(d(v), v)$.
3. Вернуть массив $d(v)$.

Ключевая деталь реализации — шаг b: поскольку у большинства реализаций min-heap нет дешёвой операции «уменьшить приоритет уже находящегося в очереди элемента», проще каждый раз при улучшении оценки просто добавлять в очередь новую пару, а старые, устаревшие записи для уже посещённых вершин игнорировать при извлечении. Это слегка увеличивает число элементов в очереди (до $O(E)$ вместо $O(V)$ в худшем случае), но не меняет асимптотику и сильно упрощает код.

import heapq

def dijkstra(graph, start):
    """
    graph: словарь вида {вершина: [(сосед, вес), ...]}
    start: стартовая вершина
    возвращает словарь кратчайших расстояний от start до каждой вершины
    """
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    visited = set()
    heap = [(0, start)]          # (расстояние, вершина)

    while heap:
        d, u = heapq.heappop(heap)

        if u in visited:
            continue              # устаревшая запись — пропускаем
        visited.add(u)

        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))

    return dist

Примеры с разбором

Пример 1. Тот же граф из шести вершин, но через код. Запустим dijkstra(graph, 'A') на графе из предыдущего раздела ($A{\to}B{:}4$, $A{\to}C{:}2$, $C{\to}B{:}1$, $B{\to}D{:}5$, $C{\to}D{:}8$, $C{\to}E{:}10$, $D{\to}E{:}2$, $D{\to}F{:}6$, $E{\to}F{:}3$). Куча последовательно проходит через состояния: после инициализации [(0,A)]; после обработки $A$ — [(2,C),(4,B)]; после обработки $C$ (с релаксациями $B{:}3$, $D{:}10$, $E{:}12$) — [(3,B),(4,B),(10,D),(12,E)] (обрати внимание — в куче осталась и устаревшая запись (4,B), она будет проигнорирована позже); после обработки $B$ (единственный минимум с учётом того, что (3,B) меньше (4,B)) — куча пополняется записью (8,D). Итоговый результат кода в точности совпадает с ручной трассировкой: $\{A{:}0, B{:}3, C{:}2, D{:}8, E{:}10, F{:}13\}$.

Пример 2. Подсчёт операций для оценки выигрыша от кучи. Пусть граф моделирует граф дружбы в социальной сети с $V = 10^6$ пользователей и $E = 5\times 10^6$ связей (в среднем 5 друзей у каждого — типичная разреженность реального социального графа). Наивная реализация потребовала бы порядка $V^2 = 10^{12}$ операций только на поиск минимумов — совершенно неприемлемо даже для современных компьютеров. Реализация с min-heap потребует порядка $(V+E)\log V \approx 6\times10^6 \times 20 \approx 1{,}2\times10^8$ операций — на много порядков меньше, вполне посильно выполнить за секунды.

Пример 3. Разбор итоговой асимптотики. За весь ход алгоритма каждое ребро релаксируется не более одного раза для каждой из версий оценки его начала (в худшем случае — до одного раза за каждую попытку улучшения), что даёт до $O(E)$ операций добавления в кучу, каждая стоимостью $O(\log E) = O(\log V)$ (поскольку $E \le V^2$, $\log E = O(\log V)$). Извлечений из кучи — тоже $O(E)$ в худшем случае (с учётом устаревших записей), каждое стоимостью $O(\log E)$. Суммарная сложность: $O((V+E)\log V)$ — именно так обычно и формулируется итоговая асимптотика алгоритма Дейкстры с приоритетной очередью на основе двоичной кучи. При использовании более экзотической структуры данных — кучи Фибоначчи — теоретическую сложность можно снизить до $O(E + V\log V)$, но на практике из-за большой константы в операциях кучи Фибоначчи редко оказываются быстрее обычной двоичной кучи для графов разумного размера.

Почему это важно. Замена структуры данных без единого изменения самой логики алгоритма — с $O(V^2)$ до $O((V+E)\log V)$ — прекрасно иллюстрирует общий принцип, который встречается в самых разных областях программирования и машинного обучения: правильный выбор структуры данных под конкретную операцию (здесь — быстрое извлечение минимума) может дать выигрыш на порядки без единого изменения алгоритмической идеи. Для разреженных графов (а таких большинство в реальных задачах) реализация с приоритетной очередью — это не «преждевременная оптимизация», а практическая необходимость: без неё алгоритм Дейкстры на графе с миллионом вершин просто не завершится за разумное время.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Дан граф с рёбрами $A\to B$ веса $3$ и $A\to C$ веса $5$. Какие значения $d(B)$ и $d(C)$ получатся сразу после инициализации алгоритма и первой релаксации рёбер из $A$ (до посещения $B$ или $C$)?

Задание 2. Сформулируй формулу релаксации ребра $(u,v)$ веса $w$ и объясни своими словами, что она делает.

Задание 3. В графе с рёбрами $A\to B$ веса $2$, $B\to C$ веса $3$, $A\to C$ веса $10$ найди кратчайшее расстояние от $A$ до $C$.

Задание 4. Почему на каждом шаге алгоритма Дейкстры выбирается непосещённая вершина именно с минимальным текущим расстоянием, а не произвольная непосещённая вершина?

Задание 5. Граф: $A\to B$ веса $4$, $A\to C$ веса $1$, $C\to B$ веса $1$. Пройди по шагам алгоритма Дейкстры от $A$ и найди итоговое $d(B)$.

Задание 6. В чём главное отличие алгоритма Дейкстры от BFS с точки зрения того, что каждый из них минимизирует?

Задание 7. Что вернёт алгоритм Дейкстры для вершины, которая физически недостижима из стартовой вершины (нет ни одного пути до неё)?

Задание 8. Что означает, что вершина «посещена» (финализирована) в алгоритме Дейкстры, и почему после этого её оценку расстояния больше нельзя менять?

Задание 9. Объясни, почему при неотрицательных весах рёбер попытка релаксировать ребро, ведущее в уже посещённую вершину, не может дать улучшения — и почему поэтому классическая реализация вообще не пытается этого делать.

Задание 10. Граф состоит из одной вершины $A$ без единого ребра. Что вернёт алгоритм Дейкстры, запущенный от $A$?

Средние (задания 11–20)

Задание 11. Дан граф: $A\to B$ веса $2$, $A\to C$ веса $6$, $B\to C$ веса $1$, $B\to D$ веса $7$, $C\to D$ веса $2$. Проведи полную трассировку алгоритма Дейкстры от $A$ и найди все итоговые расстояния.

Задание 12. Обоснуй, почему наивная реализация алгоритма Дейкстры (линейный поиск минимума среди непосещённых вершин на каждом шаге, без кучи) имеет сложность $O(V^2 + E)$.

Задание 13. Как модифицировать алгоритм Дейкстры, чтобы он возвращал не только длину кратчайшего пути, но и сам путь (последовательность вершин)?

Задание 14. В графе есть ребро $A\to B$ веса $0$ (нулевой вес). Работает ли алгоритм Дейкстры корректно в этом случае? Обоснуй.

Задание 15. Сравни асимптотическую сложность алгоритма Дейкстры с кучей ($O((V+E)\log V)$) и алгоритма Флойда-Уоршелла ($O(V^3)$, тема следующего урока). Для какого сценария каждый из них предпочтительнее?

Задание 16. В графе есть два разных пути от $A$ до $D$ одинаковой суммарной длины. Какой из них найдёт и вернёт алгоритм Дейкстры?

Задание 17. Напиши функцию на Python, выполняющую релаксацию одного ребра, принимающую текущий словарь расстояний dist, вершину u, соседа v и вес w, и возвращающую True, если релаксация улучшила оценку.

def relax(dist, u, v, w):
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        return True
    return False

Задание 18. Как правильно применить алгоритм Дейкстры к неориентированному графу (где ребро можно проходить в обе стороны)?

Задание 19. В графе есть одно отрицательное ребро, но нет ни одного отрицательного цикла. Гарантирует ли это, что алгоритм Дейкстры всё равно даст правильный ответ?

Задание 20. Граф социальной сети содержит $V=1000$ пользователей и $E=5000$ связей. Оцени порядок числа операций для алгоритма Дейкстры с кучей ($O((V+E)\log V)$) и сравни с наивной реализацией ($O(V^2)$).

Сложные (задания 21–30)

Задание 21. Дай интуитивное обоснование (без формального математического доказательства методом индукции), почему при неотрицательных весах жадный выбор минимальной непосещённой оценки на каждом шаге гарантированно приводит к глобально оптимальному результату.

Задание 22. Граф из шести вершин: $A\to B$ веса $10$, $A\to D$ веса $5$, $D\to B$ веса $3$, $D\to C$ веса $9$, $D\to E$ веса $2$, $B\to C$ веса $1$, $C\to F$ веса $4$, $E\to F$ веса $6$, $E\to D$ веса $7$. Проведи полную трассировку от $A$ с явным указанием содержимого приоритетной очереди на каждом шаге.

Задание 23. Как модифицировать алгоритм Дейкстры, если нужно найти кратчайший путь только до одной конкретной целевой вершины $t$, а не до всех вершин графа? Какая оптимизация здесь возможна?

Задание 24. В ориентированном графе есть цикл положительного суммарного веса (например, $X\to Y$ веса $3$, $Y\to X$ веса $2$, суммарно $+5$ за цикл). Как это влияет на работу алгоритма Дейкстры?

Задание 25. Сравни теоретическую сложность реализации на основе обычной двоичной кучи ($O((V+E)\log V)$) и на основе кучи Фибоначчи ($O(E+V\log V)$). Для каких графов разница становится значимой, и почему на практике куча Фибоначчи используется редко?

Задание 26. Опиши идею двунаправленного (bidirectional) поиска Дейкстры для ускорения нахождения кратчайшего пути между двумя конкретными вершинами $s$ и $t$.

Задание 27. Приведи конкретный практический пример из области машинного обучения или анализа данных, где нужен именно алгоритм Дейкстры, а не BFS.

Задание 28. В графе веса рёбер — это вероятности успешного перехода (числа от $0$ до $1$), и нужно найти путь, максимизирующий произведение вероятностей вдоль пути (а не сумму). Как свести эту задачу к стандартному алгоритму Дейкстры?

Задание 29. Объясни, почему при весе каждого ребра, равном ровно единице ($w=1$ для всех рёбер), алгоритм Дейкстры по своему поведению полностью совпадает с BFS.

Задание 30. Спроектируй (опиши на уровне архитектуры, без кода) систему маршрутизации логистической сети, где веса рёбер графа дорог предсказываются отдельной ML-моделью, а поиск маршрута выполняется алгоритмом Дейкстры. Какие компоненты нужны и как они взаимодействуют?

Частые ошибки

❌ Ошибка: Применить алгоритм Дейкстры напрямую к графу с отрицательными весами рёбер, не проверив это условие заранее.

✅ Правильно: Перед запуском алгоритма всегда проверять, что все веса рёбер графа неотрицательны; при наличии хотя бы одного отрицательного веса использовать алгоритм Беллмана-Форда (или, если граф — DAG, специализированный алгоритм на основе топологической сортировки).

💡 Почему: Как показывает контрпример этого урока (граф $A\to B$ веса $1$, $A\to C$ веса $2$, $C\to B$ веса $-2$), классический алгоритм Дейкстры может зафиксировать неверное, завышенное расстояние до вершины и никогда его не исправить — и никакого предупреждения об ошибке при этом не будет, результат просто окажется тихо неверным.

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

✅ Правильно: Как только вершина помечена как посещённая, её оценка расстояния окончательна и релаксация в неё больше не выполняется — при корректной реализации.

💡 Почему: Повторная релаксация посещённых вершин при неотрицательных весах никогда не даёт улучшения (см. разбор в задании 9), поэтому лишний код для этого не нужен — но если веса всё же отрицательны, попытка «досрочно» пересмотреть уже посещённую вершину — это фактически превращение алгоритма во что-то похожее на Беллмана-Форда, только с некорректной, неполной логикой.

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

✅ Правильно: Для разреженных графов всегда использовать реализацию с приоритетной очередью (min-heap), дающую $O((V+E)\log V)$ вместо $O(V^2)$.

💡 Почему: Разница между этими двумя асимптотиками на графе с миллионом вершин и несколькими миллионами рёбер — это разница между долями секунды и часами вычислений; при разреженном графе ($E \ll V^2$) выигрыш от кучи не опциональный бонус, а практическая необходимость.

❌ Ошибка: Забыть, что нужно пропускать устаревшие записи в приоритетной очереди (когда одна и та же вершина добавлена в очередь несколько раз с разными оценками расстояния до неё).

✅ Правильно: При извлечении элемента из очереди всегда проверять, не была ли эта вершина уже посещена ранее — если да, просто пропускать эту запись и переходить к следующей.

💡 Почему: Без такой проверки алгоритм может повторно «обработать» вершину с устаревшей (уже неактуальной, большей) оценкой расстояния, что как минимум приводит к лишним вычислениям, а в некоторых неаккуратных реализациях — и к неверному итоговому результату.

❌ Ошибка: Путать задачу «кратчайший путь от одной вершины до всех остальных» (задача Дейкстры) с задачей «кратчайшие пути между всеми парами вершин» (задача следующего урока, алгоритм Флойда-Уоршелла), и пытаться получить полную матрицу расстояний одним запуском Дейкстры.

✅ Правильно: Если нужна полная матрица расстояний между всеми парами вершин, либо запускать алгоритм Дейкстры отдельно из каждой вершины ($V$ запусков, итоговая сложность $O(V(V+E)\log V)$), либо, при подходящем размере графа, использовать алгоритм Флойда-Уоршелла с $O(V^3)$ за один проход.

💡 Почему: Один запуск алгоритма Дейкстры принципиально даёт расстояния только от одной заданной стартовой вершины — не путай масштаб задачи, которую решает конкретный запуск алгоритма.

❌ Ошибка: Считать, что алгоритм Дейкстры работает и на неориентированных графах «как есть», без каких-либо изменений в представлении графа.

✅ Правильно: Каждое неориентированное ребро нужно явно представить как пару противоположно направленных ориентированных рёбер с одинаковым весом (см. задание 18) — тогда алгоритм применяется без изменений в логике.

💡 Почему: Если забыть добавить ребро «в обе стороны» в структуре данных графа (например, в списке смежности), часть путей окажется физически недостижимой для алгоритма, даже если в исходной задаче переход был возможен в обе стороны.

Главное запомнить

✅ Алгоритм Дейкстры решает задачу поиска кратчайшего пути от одной стартовой вершины до всех остальных во взвешенном графе с неотрицательными весами рёбер

✅ Идея алгоритма — жадная: на каждом шаге фиксируется непосещённая вершина с минимальной текущей оценкой расстояния, поскольку при неотрицательных весах эта оценка гарантированно уже окончательна

✅ Релаксация ребра $(u,v)$ веса $w$ — единственная операция, изменяющая оценки расстояний: $d(v) \leftarrow \min(d(v), d(u)+w)$

✅ Как только вершина посещена (зафиксирована), её оценка расстояния больше никогда не меняется — это ключевое инвариантное свойство алгоритма

✅ Алгоритм не работает корректно при отрицательных весах рёбер: жадная фиксация может произойти раньше, чем найдётся более дешёвый путь через отрицательное ребро; для таких графов используется алгоритм Беллмана-Форда

✅ При наличии в графе цикла отрицательного суммарного веса задача о кратчайшем пути вообще теряет смысл (расстояние стремится к $-\infty$)

✅ Наивная реализация с линейным поиском минимума имеет сложность $O(V^2 + E)$; реализация с приоритетной очередью (min-heap) ускоряет её до $O((V+E)\log V)$, что критично для разреженных графов

✅ При единичных весах всех рёбер алгоритм Дейкстры вырождается в обычный BFS — это частный случай более общего алгоритма

✅ Алгоритм Дейкстры лежит в основе навигационных систем, протоколов маршрутизации в компьютерных сетях (OSPF), а также поиска кратчайших цепочек связей в графах социальных сетей и рекомендательных системах

✅ Для восстановления не только длины, но и самого пути, нужен дополнительный массив предшественников (parent), обновляемый при каждой успешной релаксации

Связь с темами курса

🔙 Откуда пришли: Из урока 262 — топологическая сортировка дала тебе инструмент упорядочивания вершин DAG по зависимостям; для DAG (без циклов) существует ещё более быстрый специализированный алгоритм кратчайшего пути, использующий именно топологический порядок вместо приоритетной очереди. Урок 261 (обход графов, DFS и BFS) заложил базовое понимание обхода графов и уже указывал, что BFS решает задачу кратчайшего пути только для невзвешенных графов — этот урок закрывает именно тот пробел, о котором там шла речь.

🔜 Куда идём: Следующий урок 264 — алгоритм Флойда-Уоршелла, решающий более общую задачу поиска кратчайших путей сразу между всеми парами вершин графа за один проход динамического программирования; полезно сразу сравнивать его $O(V^3)$ с $O(V(V+E)\log V)$ при $V$ запусках Дейкстры и понимать, когда какой подход выгоднее. Дальше в курсе алгоритмов — минимальное остовное дерево (урок 265), задача, исторически описанная Дейкстрой в той же статье 1959 года, где очень похожая жадная идея применяется не к поиску кратчайшего пути, а к минимизации суммарного веса рёбер, соединяющих все вершины графа.

🎯 В машинном обучении: Кратчайшие пути в графах — фундаментальный инструмент за пределами навигации: в рекомендательных системах на основе графов кратчайший путь между пользователями используется как признак близости и как основа объяснимых рекомендаций («вы связаны через N общих контактов»); в сетевом анализе кратчайшие пути лежат в основе метрик центральности узлов (betweenness centrality), применяемых для анализа влиятельности в графах знаний и социальных сетях; в задачах маршрутизации логистики ML-модели предсказывают динамические веса рёбер (время в пути, стоимость), которые затем напрямую подаются на вход алгоритму Дейкстры для построения оптимального маршрута — прямая связка между машинным обучением и классическим алгоритмом на графах.

Интересные факты

📌 Алгоритм был придуман Эдсгером Дейкстрой в 1956 году за примерно двадцать минут, пока он сидел с невестой в кафе в Амстердаме без бумаги и карандаша — именно отсутствие письменных принадлежностей, по его собственному признанию, заставило искать решение, которое можно было полностью удержать в голове, что и предопределило удивительную простоту итогового алгоритма.

📌 Опубликован алгоритм был лишь три года спустя, в 1959 году, в статье объёмом всего три страницы — притом что в этой же статье Дейкстра описал ещё один результат, алгоритм построения минимального остовного дерева, очень похожий на алгоритм Прима.

📌 Изначально Дейкстра придумал алгоритм для демонстрации возможностей компьютера ARMAC на упрощённой карте Нидерландов с 64 городами — не как самостоятельное научное исследование, а как эффектную иллюстрацию для широкой публики, и лишь спустя десятилетия алгоритм стал одним из самых широко используемых в истории информатики.

📌 Протокол маршрутизации OSPF (Open Shortest Path First), используемый внутри крупных интернет-провайдеров и корпоративных сетей по всему миру, в буквальном смысле реализует алгоритм Дейкстры: каждый маршрутизатор в сети регулярно строит собственное дерево кратчайших путей до всех остальных узлов сети на основе весов (задержек) соединений.

📌 Изначальный алгоритм Дейкстры имел сложность $O(V^2)$ и был опубликован задолго до того, как приоритетные очереди на основе двоичных куч стали стандартным инструментом информатики; современная оптимизация с использованием min-heap, дающая $O((V+E)\log V)$, — это уже более поздняя инженерная надстройка над исходной идеей 1956 года.

Лайфхаки

💡 Чтобы быстро проверить, применим ли алгоритм Дейкстры к конкретному графу, задай себе один вопрос: могут ли веса рёбер быть отрицательными хотя бы теоретически (даже если в текущих данных их нет)? Если ответ «да» — либо гарантируй неотрицательность весов на уровне данных заранее, либо сразу переключайся на алгоритм Беллмана-Форда, не тратя время на отладку загадочно неверных результатов Дейкстры.

💡 При отладке собственной реализации алгоритма полезно писать функцию-валидатор, которая после завершения работы проверяет для каждого ребра $(u,v)$ веса $w$ условие $d(v) \le d(u) + w$ (неравенство треугольника для кратчайших путей) — если оно нарушено хотя бы для одного ребра, значит в реализации есть ошибка (или граф содержит отрицательные веса, с которыми алгоритм несовместим).

💡 На собеседованиях по алгоритмам вопрос «а что если веса отрицательные?» задают чрезвычайно часто именно после разбора алгоритма Дейкстры — заранее подготовленный контрпример (три вершины, как в этом уроке) с чётким объяснением, почему ранняя фиксация вершины ломает корректность, производит гораздо более сильное впечатление, чем простое «он не работает с отрицательными весами».

💡 Если в языке программирования нет встроенной приоритетной очереди с операцией decrease-key (как в Python с модулем heapq), не пытайся реализовывать её вручную — гораздо проще и надёжнее использовать приём «ленивого удаления»: просто каждый раз добавлять в очередь новую запись при улучшении оценки, а устаревшие записи для уже посещённых вершин пропускать при извлечении (именно так устроен код в этом уроке).

💡 Если нужно решить конкретную практическую задачу поиска кратчайшего пути на реальных данных, в подавляющем большинстве случаев не стоит реализовывать алгоритм Дейкстры с нуля — библиотеки вроде networkx в Python (функция dijkstra_path) или scipy.sparse.csgraph.dijkstra предоставляют оттестированные и оптимизированные реализации; понимание внутреннего устройства алгоритма нужно не для того, чтобы писать его заново в продакшене, а для того, чтобы правильно выбирать между доступными инструментами и понимать границы их применимости.

💡 Если задача требует найти путь не только с минимальной суммой весов, но и максимизирующий или минимизирующий что-то ещё нелинейное (например, произведение вероятностей, как в задании 28), почти всегда можно свести её к стандартной постановке Дейкстры через подходящее математическое преобразование весов (чаще всего — через логарифм) — прежде чем изобретать совершенно новый алгоритм, стоит поискать такое сведение.

Алгоритм, родившийся за двадцать минут в амстердамском кафе без единого листа бумаги, сегодня работает внутри каждого навигатора в твоём телефоне, внутри маршрутизаторов, передающих через интернет этот самый текст, и внутри рекомендательных систем, которые каждый день предлагают тебе новых людей и товары на основе кратчайших цепочек связей в огромных графах. Ты увидел не просто последовательность шагов, а работающую математическую гарантию: почему жадный выбор ближайшей вершины при неотрицательных весах доказуемо приводит к глобально верному ответу, и почему та же самая логика рассыпается при малейшем нарушении этого условия. Это понимание — когда жадность работает, а когда нет, — окажется ценным далеко за пределами графовых алгоритмов, в любой задаче, где приходится выбирать между быстрым локальным решением и более дорогим, но универсально корректным. Дальше в курсе эта же идея кратчайших путей развернётся в более общую задачу — поиск расстояний сразу между всеми парами вершин графа, — а сам принцип автоматического построения оптимальных маршрутов по динамически изменяющимся, предсказанным моделями весам останется одним из самых практичных мостов между классическими алгоритмами и машинным обучением.