EssayAI
Блог
Блог
Математика и алгоритмы

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

8 ноября 2026Время чтения: 8 минут
#алгоритм флойда-уоршелла#кратчайший путь#теория графов#динамическое программирование#матрица расстояний
Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла находит кратчайшие расстояния между всеми парами вершин взвешенного графа. Он последовательно разрешает использовать новые промежуточные вершины и уточняет таблицу расстояний. Отрицательные веса рёбер допустимы, если интересующие маршруты не затронуты отрицательным циклом. В интерактивной матрице ниже можно проследить, какие значения меняются после каждого этапа.

Почему нужна матрица расстояний

Представьте сеть переходов между несколькими пунктами. Если надо ответить только на один вопрос «как добраться из А в Г?», вычисление всех пар может быть излишним. Но для множества запросов по одной неизменной сети удобно заранее получить таблицу: строка обозначает начало, столбец - конец, а ячейка содержит минимальную суммарную стоимость маршрута.

Граф может быть ориентированным: ребро А → Б само по себе не означает существование ребра Б → А. Поэтому матрица расстояний в общем случае не симметрична. Значение ∞\infty означает отсутствие пути, а ноль на диагонали соответствует пустому пути из вершины в себя. Нулевое ребро при этом тоже возможно: отсутствие ребра нельзя кодировать просто нулём.

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

Матрица начинается с весов рёбер; после разрешения Б и В выделяются уменьшившиеся расстояния, затем показ возвращается к началу.

Идея: добавляем разрешённые вершины

Пусть вершины пронумерованы от 11 до nn. Обозначим через dij(k)d_{ij}^{(k)} минимальную длину пути из ii в jj, внутренние вершины которого разрешено выбирать только среди первых kk вершин. Начало и конец маршрута не ограничены этим условием. При k=0k=0 внутри пути не может быть вершин: доступны только прямые рёбра и пустые пути.

Когда разрешается вершина kk, есть две возможности. Лучший путь либо не использует её внутри и сохраняет прежнюю стоимость, либо проходит через неё и складывается из пути i→ki \to k и пути k→jk \to j. Поэтому

dij(k)=min⁡(dij(k−1), dik(k−1)+dkj(k−1)).d_{ij}^{(k)}=\min\left(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right).

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

Начальная таблица и порядок циклов

Для каждой пары сначала записывают вес прямого ребра. Если параллельных рёбер несколько, выбирают минимальный вес; если ребра нет, записывают ∞\infty. На диагонали ставят минимум из нуля и веса петли, если она есть: отрицательная петля уже является отрицательным циклом.

для k от 1 до n:
    для i от 1 до n:
        для j от 1 до n:
            если d[i][k] и d[k][j] конечны:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Внешний цикл именно по kk: к началу очередного этапа должны быть рассмотрены все пары для предыдущего набора промежуточных вершин. Циклы по ii и jj внутри него можно поменять местами. Если отрицательных циклов нет, обновлять одну матрицу на месте корректно: на этапе kk диагональ dkk=0d_{kk}=0, поэтому нужные расстояния до kk и от неё не улучшаются за счёт самой kk.

Проверка конечности особенно важна, когда вместо настоящей бесконечности в программе используют большое целое число. Иначе выражение «бесконечность плюс отрицательный вес» может ошибочно стать меньше выбранного заменителя бесконечности. Кроме того, тип чисел должен вмещать суммы весов без переполнения.

Разбор четырёх вершин

Возьмём ориентированные рёбра А → Б с весом 3, А → В с весом 8, А → Г с весом 10, Б → В с весом −2, Б → Г с весом 7 и В → Г с весом 2. Других рёбер нет. Этот учебный граф не содержит циклов: каждое ребро идёт только вперёд по перечисленному порядку.

На старте путь А → В стоит 8. Разрешение А ничего не меняет. Затем разрешаем Б и сравниваем прямой путь с обходом через неё: 3+(−2)=13+(-2)=1, поэтому в клетке А → В записываем 1. Для А → Г обход через Б пока стоит 3+7=103+7=10, то есть не улучшает прямое ребро.

На этапе В используется уже уточнённое значение А → В. Через В получаем 1+2=31+2=3, и расстояние А → Г уменьшается с 10 до 3. Аналогично Б → Г уменьшается с 7 до −2+2=0-2+2=0. Разрешение Г больше ничего не меняет. Итоговая таблица показана на рисунке: знак ∞\infty в ней означает, что обратного пути нет, а не то, что вычисления ещё не закончились.

Итоговая матрица расстояний четырёх вершин: путь А через Б и В в Г имеет вес 3
Итоговая матрица расстояний четырёх вершин: путь А через Б и В в Г имеет вес 3

В ползунке можно остановиться на любом этапе и сопоставить ячейку с исходными рёбрами. На этапе Б подсвечена клетка А → В, на этапе В - клетки А → Г и Б → Г. Важна не только итоговая цифра: она появилась благодаря ранее найденному подпути.

Как восстановить сам маршрут

Матрица расстояний отвечает на вопрос о стоимости, но не хранит достаточно информации, чтобы однозначно перечислить вершины пути. Для восстановления заведите матрицу nextnext: для прямого ребра i→ji \to j запишите в next[i][j]next[i][j] вершину jj, а для недостижимой пары - специальное пустое значение.

Если обход через kk строго уменьшил расстояние i→ji \to j, обновите вместе с расстоянием и первый шаг: next[i][j]=next[i][k]next[i][j] = next[i][k]. После вычислений начинайте в ii, переходите к next[i][j]next[i][j] и повторяйте до достижения jj. Для примера получится А → Б → В → Г, а сумма весов равна 3. При нескольких равных по стоимости маршрутах правило строгого улучшения сохраняет один из них; его выбор зависит от начального представления и порядка рассмотрения.

Если next[i][j]next[i][j] пуст, пути нет. Если пара затронута отрицательным циклом, восстанавливать конечный кратчайший маршрут нельзя: его стоимость не ограничена снизу. Практическая реализация должна проверить это до восстановления и иметь защиту от бесконечного обхода при повреждённых данных.

Отрицательные циклы и область их влияния

Отрицательное ребро само по себе не мешает алгоритму, как видно по ребру Б → В. Но если можно обойти цикл с отрицательной суммой рёбер, стоимость прогулки через него можно уменьшать сколь угодно долго. После обычного прохода отрицательное значение d[t][t]d[t][t] указывает на достижимый из tt отрицательный замкнутый обход.

Однако наличие такого цикла не делает бессмысленными все пары графа. Расстояние из ii в jj не ограничено снизу именно тогда, когда существует вершина tt с d[t][t]<0d[t][t]<0, до которой можно добраться из ii и из которой можно добраться до jj. Такие пары обычно помечают отдельно как −∞-\infty; недостижимые пары остаются +∞+\infty. В неориентированном графе отрицательное ребро, доступное в обоих направлениях, уже позволяет получить отрицательный замкнутый обход.

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

Сложность и выбор метода

Три вложенных цикла дают O(n3)O(n^3) времени, а таблица расстояний занимает O(n2)O(n^2) памяти; матрица следующих вершин добавляет ещё O(n2)O(n^2). Это удобно для небольших и плотных графов, когда нужны ответы для многих пар. После предвычисления стоимость конкретного расстояния читается из одной ячейки за O(1)O(1), хотя вывод маршрута занимает время по числу его рёбер.

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

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

  • Менять порядок циклов так, что kk оказывается внутри: нарушается смысл этапа динамического программирования.
  • Считать отсутствие ребра нулевым весом или забывать направление ребра.
  • Складывать фиктивную целочисленную бесконечность с весом без проверки и допускать переполнение.
  • Считать любое отрицательное ребро отрицательным циклом либо объявлять все пары испорченными из-за одного цикла.
  • Пытаться восстановить маршрут только по числу в матрице расстояний без дополнительных данных.

FAQ

Работает ли алгоритм с отрицательными весами? Да, если для рассматриваемой пары нельзя пройти через отрицательный цикл. Веса рёбер могут быть отрицательными, нулевыми или положительными.

Нужна ли новая матрица на каждом этапе? Нет. При отсутствии отрицательных циклов достаточно обновлять одну матрицу на месте. Отдельные снимки удобны для обучения и проверки промежуточных результатов.

Что означает бесконечность в итоговой таблице? Из вершины строки нельзя попасть в вершину столбца. Это отличается от −∞-\infty, которым помечают пары, чья стоимость не ограничена снизу из-за отрицательного цикла.

Коротко

Флойд-Уоршелл разрешает промежуточные вершины по одной и для каждой пары сравнивает старое расстояние с обходом через очередную вершину. За O(n3)O(n^3) времени и O(n2)O(n^2) памяти он строит матрицу расстояний; дополнительная матрица позволяет восстановить маршруты, а проверка диагонали помогает обнаружить отрицательные циклы.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

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

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

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

18 января 202610 минут
Граф Кэли: как построить граф группы

Граф Кэли: как построить граф группы

Граф Кэли связывает операции группы с вершинами и рёбрами. Разбираем построение на вычетах по модулю 8, связность, кратчайшие пути и выбор образующих.

8 ноября 20268 минут
Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера строит эйлеров путь или цикл в графе. Разбираем условия существования, работу стека, пример с двумя циклами и сложность алгоритма.

8 ноября 20268 минут
Дерево: свойства и число рёбер

Дерево: свойства и число рёбер

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

8 ноября 20268 минут
Формула Эйлера для планарных графов

Формула Эйлера для планарных графов

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

8 ноября 20268 минут
Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток алгоритмом Форда-Фалкерсона: разбираем остаточную сеть, обратные рёбра и дополняющие пути на примере, а результат проверяем разрезом.

8 ноября 20269 минут