Кратчайшие пути: алгоритмы Дейкстры и Флойда-Уоршелла

Навигатор за доли секунды отвечает на вопрос «как быстрее до центра» — хотя вариантов маршрута больше, чем атомов в песочнице. В его сердце лежит алгоритм 1959 года, придуманный голландским программистом Эдсгером Дейкстрой за двадцать минут в кафе. Задача о кратчайших путях — самая запрашиваемая задача на графах: маршрутизация пакетов, логистика, карты, планирование. Разберём два её измерения: от одной вершины до всех и от всех до всех.

Постановка задачи#

Дан взвешенный граф: рёбра несут неотрицательные веса — километры, минуты, цена билета. Кратчайший путь из $s$ в $t$ — маршрут с минимальной суммой весов. Вариантов задачи три: один старт — один финиш; один старт — все вершины; все — все. Дейкстра решает второй вариант (а заодно и первый), Флойд — третий. В основах графов мы уже упоминали: в невзвешенном графе кратчайшие пути даёт BFS — Дейкстра и есть его обобщение на взвешенный случай.

Алгоритм Дейкстры: жадность с гарантией#

Идея: расти облако «обработанных» вершин, начиная со старта. На каждом шаге:

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

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

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

Дейкстра вручную: маленький числовой граф#

Пройдём алгоритм руками на графе из четырёх вершин. Рёбра: AB=2, AC=5, BC=1, BD=6, CD=2. Старт — A.

Обратите внимание на шаг 3: прямое ребро AC длиной 5 было в ответах, пока не нашёлся объезд A→B→C длиной 3. Релаксация — это и есть механизм «услышал про более дешёвый маршрут — исправился».

Флойд-Уоршелл: все пути сразу#

Дейкстру можно запустить из каждой вершины — получится $O(n\cdot m\log n)$. Но есть изящный приём динамического программирования — алгоритм Флойда-Уоршелла. Он держит матрицу $d[i][j]$ — текущее расстояние от $i$ до $j$ (см. словарную статью матрица — тут вся механика табличная) и постепенно разрешает вершины-«пересадки»:

Расшифровка: после $k$ итераций $d[i][j]$ — кратчайшее расстояние от $i$ до $j$ среди путей, которым разрешено останавливаться только в вершинах $1,\dots ,k$. Каждая вершина $k$ либо ничего не меняет, либо даёт новый маршрут «из $i$ в $k$, потом из $k$ в $j$». Три вложенных цикла — $k$, $i$, $j$ — и сложность ровно $O(n^3)$ при памяти $O(n^2)$. Код занимает пять строк — поэтому Флойд любимец экзаменаторов: коротко, и есть что анализировать.

Как выбирать? Нужен один маршрут по городу — Дейкстра. Нужно расстояние между всеми парами (например, таблица тарифов между городами) и граф небольшой — Флойд. Граф невзвешенный — хватит BFS. Появились отрицательные веса — Беллман-Форд или Флойд.

Прогоним Флойда на крошечном графе из трёх вершин, чтобы механика перестала быть абстрактной. Рёбра: AB = 2, BC = 3, и «прямое» AC = 10. Начальная матрица: $d[A][B]=2$, $d[B][C]=3$, $d[A][C]=10$, диагональ нулевая, остальное $\infty$. Разрешаем пересадку через B: $d[A][C]=\min (10,2+3)=5$ — тариф упал вдвое. Пересадки через A и через C ничего не меняют. Итоговая матрица: AB = 2, BC = 3, AC = 5. Одна итерация — и вся таблица расстояний готова.

Пара слов о масштабе. Граф с 1000 вершинами и 5000 рёбрами: Дейкстра с кучей сделает порядка $m\log n\approx 5000\cdot 10=50000$ операций — мгновенно. Флойд потребует $10^9$ обновлений — секунды и большие таблицы. Поэтому навигаторы используют вариант Дейкстры, а точнее его развитие с эвристикой — A*: оценка «расстояние по прямой до цели» подсказывает, какие вершины развивать первыми, и оптимум не страдает, если эвристика не завышает. Тот же приём — двунаправленный поиск от старта и от финиша навстречу.

Мостик к практике: Дейкстра живёт не только в навигаторах. Протокол OSPF раскладывает маршруты в интернете именно ею, в системах сборки кода так ищут кратчайшую цепочку зависимостей, а логистические сервисы считают ей стоимость доставки до каждого склада сразу. Тема продолжается естественно: в уроке об обходах графов BFS и DFS показаны на тех же графах, только без весов, — после Дейкстры они читаются как букварь. И проверьте себя на симуляторе выше: найдите в графе «city» пару вершин, для которых прямой маршрут дороже объезда.

• «Один ко всем» — Дейкстра (или BFS без весов); «все ко всем» — Флойд.
• Жадность Дейкстры опирается на неотрицательность весов: минимум нельзя улучшить через более дальних.
• Релаксация — единственная операция обоих алгоритмов: услышал про дешевле — исправь.
• Путь восстанавливается предками (Дейкстра) или матрицей next (Флойд) — длины без маршрута на защите лабораторной недостаточно.
• Отрицательные веса: Беллман-Форд вместо Дейкстры; отрицательный цикл — «кратчайшего пути не существует».

1. 1
   На каждом шаге фиксируется ровно одна вершина — та, чья метка минимальна среди необработанных. Если выбрали не минимум — алгоритм уже сломан.
2. 2
   После каждой релаксации метка может только уменьшиться. Увеличилась — ищите ошибку в сложении весов.
3. 3
   Метка фиксированной вершины больше не меняется никогда. Улучшали её позже — значит, нарушили порядок фиксации.
4. 4
   Контрольная проверка: пройдите по найденному маршруту и сложите веса вручную — сумма обязана совпасть с меткой финиша.
5. 5
   Финальный тест на понимание: попробуйте объяснить, почему на третьем шаге числового примера выше метка C улучшилась через B, а не осталась прямой пятёркой от A.