Алгоритм Флойда-Уоршелла 🗺️
В прошлом уроке ты разобрал алгоритм Дейкстры — он отвечает на вопрос «как быстрее всего добраться из вершины A во все остальные вершины графа». Но реальные задачи часто ставят вопрос иначе: логистической компании не нужен кратчайший путь от одного конкретного склада — ей нужна ПОЛНАЯ таблица кратчайших расстояний между каждой парой из сотен складов и магазинов сразу, чтобы в любой момент мгновенно подобрать оптимальный маршрут доставки. Социальной сети нужно знать «степень разделения» между всеми парами пользователей одновременно, а не только между одним выбранным человеком и остальными. Формально: если Дейкстра решает задачу с одним источником (кратчайшие пути от одной вершины ко всем остальным), то задача поиска кратчайших путей между всеми парами вершин — это другая, более широкая постановка, и наивное решение «запустить Дейкстру из каждой вершины по очереди» далеко не всегда оптимально, а иногда и вовсе неприменимо.
Алгоритм Флойда-Уоршелла решает именно эту более широкую задачу — причём делает это на удивление простым кодом из трёх вложенных циклов, без очередей с приоритетом, без сортировки рёбер и без специальных структур данных. За этой простотой стоит одна из самых красивых и самых тиражируемых идей в алгоритмике — динамическое программирование: разбить сложную задачу «найти кратчайший путь через что угодно» на последовательность простых задач «а что если разрешить пути проходить только через первую вершину? А через первые две? А через первые три?» — и постепенно, шаг за шагом, расширять множество разрешённых промежуточных вершин, пока оно не станет включать в себя весь граф целиком.
Есть и вторая причина, по которой этот алгоритм заслуживает отдельного разбора: в отличие от Дейкстры, он корректно работает с отрицательными весами рёбер. Это не второстепенная деталь — это открывает целый класс задач, которые Дейкстре принципиально не под силу: поиск арбитражных циклов на валютном рынке (где «вес» ребра — это логарифм обменного курса, который вполне может быть отрицательным), задачи с рёбрами-«кэшбэками» или «бонусами», где переход между состояниями может уменьшать накопленную стоимость. Но у этой силы есть и обратная сторона: если в графе существует отрицательный цикл — цикл, суммарный вес рёбер которого меньше нуля, — само понятие «кратчайший путь» перестаёт быть корректно определённым, потому что можно бесконечно наматывать круги по этому циклу, уменьшая длину пути сколь угодно сильно. Флойд-Уоршелл умеет не только находить кратчайшие пути в «здоровых» графах, но и элегантно обнаруживать наличие такого патологического цикла — и это умение почти так же ценно, как сам поиск расстояний.
Наконец, важно честно обозначить и ограничение: сложность алгоритма — $O(V^3)$ по времени, где $V$ — число вершин, что делает его непрактичным для по-настоящему огромных графов из сотен тысяч вершин. Понимание того, когда Флойд-Уоршелл выигрывает у многократного запуска Дейкстры, а когда проигрывает, — не менее важная часть этого урока, чем сама механика алгоритма.
🎯 Ты узнаешь:
- Чем задача поиска кратчайших путей между всеми парами вершин принципиально отличается от задачи с одним источником, которую решает Дейкстра
- Идею динамического программирования, лежащую в основе алгоритма, и его рекуррентную формулу $dist[i][j] = \min(dist[i][j],\ dist[i][k] + dist[k][j])$
- Как алгоритм работает с отрицательными весами рёбер и почему это принципиально недоступно Дейкстре
- Как обнаружить отрицательный цикл в графе, используя тот же самый алгоритм без каких-либо дополнений
- Когда честно выгоднее использовать Флойд-Уоршелл, а когда — многократный запуск Дейкстры или алгоритм Джонсона
- Как та же самая идея динамического программирования «по возрастающему множеству разрешённых переходов» применяется в биоинформатике, обработке естественного языка и сетевом анализе
История: откуда это взялось?
Алгоритм носит двойное имя — Флойда и Уоршелла, — и это не случайность редактора учебника, а отражение того, что один и тот же математический трюк был независимо переоткрыт как минимум трижды за считаные годы, причём для решения на первый взгляд совершенно разных задач. Роберт Флойд, американский специалист по информатике, в 1962 году опубликовал короткую заметку с описанием кратчайшего пути в одном из ведущих научных журналов по вычислительной технике — она занимала меньше страницы и описывала именно ту рекуррентную схему с промежуточными вершинами, которую ты изучишь в этом уроке, применительно к поиску кратчайших расстояний во взвешенном графе. Флойд позже стал одной из самых влиятельных фигур в теоретической информатике: в 1978 году он получил премию Тьюринга — самую престижную награду в области информатики — за вклад в методологию создания эффективного и надёжного программного обеспечения, включая технику формальной верификации программ через индуктивные утверждения. Кроме алгоритма кратчайших путей, его имя носит ещё как минимум два широко используемых метода — алгоритм обнаружения цикла в связном списке («черепаха и заяц») и алгоритм построения кучи за линейное время.
Стивен Уоршелл в том же 1962 году решал задачу, которая формально выглядит совсем иначе: не поиск расстояний, а транзитивное замыкание — вопрос «достижима ли вершина j из вершины i хоть каким-нибудь путём», без учёта весов вообще, просто да или нет. Его статья о теореме про булевы матрицы показывала, как булеву матрицу смежности можно превратить в булеву матрицу достижимости той же самой схемой: рассматривая промежуточные вершины по очереди и обновляя матрицу правилом «i достигает j, если i уже достигает j напрямую, или i достигает k, а k достигает j». Разница между задачей Уоршелла и задачей Флойда — это разница между логическим «И/ИЛИ» и арифметическим «плюс/минимум», но структура рекурсии в обеих задачах идентична буква в букву, и именно поэтому два независимо открытых результата со временем срослись в один алгоритм с двумя именами в заголовке. Забавная деталь: за несколько лет до них, в 1959 году, французский математик Бернар Рой опубликовал практически тот же результат в статье на французском языке — поэтому в некоторых источниках, особенно европейских, алгоритм иногда называют алгоритмом Роя-Уоршелла или Роя-Флойда-Уоршелла, отдавая дань и этому более раннему, но менее замеченному международным сообществом открытию.
Показательно, что ни один из троих не думал о своей работе как о «прорыве» — каждая публикация занимала одну-две страницы и выглядела скорее технической заметкой, чем эпохальным трудом. Но именно эта скромная по объёму идея — постепенно расширять множество разрешённых промежуточных вершин и пересчитывать матрицу целиком на каждом шаге — оказалась настолько фундаментальной, что сегодня она преподаётся на первом курсе почти любой программы по информатике и служит хрестоматийным примером того, как выглядит динамическое программирование в его самом чистом виде.
Задача о кратчайших путях между всеми парами вершин
Интуиция: от одной точки — ко всей карте сразу
Представь себе почтовую службу, которая обслуживает $200$ городов. Если бы её интересовало расстояние только от главного распределительного центра до каждого из этих городов, хватило бы одного запуска алгоритма Дейкстры — ровно так этот алгоритм и задуман: один источник, множество приёмников. Но реальная логистическая сеть работает не по схеме «звезда из одного центра» — посылка может двигаться напрямую между любыми двумя городами, и диспетчеру нужна возможность мгновенно узнать кратчайшее расстояние между произвольной парой городов A и B, где ни A, ни B заранее не фиксированы. Хранить заранее посчитанную таблицу «откуда — куда — сколько» и обращаться к ней за $O(1)$ — вот что на самом деле требуется, а не повторный запуск поиска пути каждый раз, когда приходит новый запрос.
Наивное решение выглядит соблазнительно простым: раз Дейкстра умеет находить кратчайшие пути от одной вершины до всех остальных, просто запусти её по очереди из каждой из $V$ вершин графа — и получишь всю таблицу. Формально это работает, и для многих графов это даже разумный выбор (к честному сравнению мы вернёмся в отдельном разделе ниже). Но у такого подхода есть слабое место: он требует $V$ полностью независимых запусков алгоритма, каждый из которых заново обходит граф, заново строит очередь с приоритетом и не переиспользует вообще никакую информацию, вычисленную на предыдущих запусках — хотя интуитивно кажется, что кратчайшие пути из разных вершин часто проходят через одни и те же «узловые» точки графа, и было бы неплохо считать эту общую информацию один раз, а не $V$ раз заново.
Флойд-Уоршелл устроен принципиально иначе: он не запускает $V$ независимых процедур поиска, а с самого начала работает сразу со всей матрицей расстояний $n \times n$ целиком, обновляя все $n^2$ пар одновременно на каждом шаге. Вместо вопроса «как добраться из конкретной вершины A во все остальные» алгоритм с первой же строчки кода отвечает на вопрос «как изменится представление о кратчайших расстояниях между ВСЕМИ парами, если разрешить путям проходить через ещё одну конкретную вершину-посредника». Это смещение точки зрения — с «одна стартовая вершина» на «одна дополнительная разрешённая промежуточная вершина» — и есть ключевая идея, которая позволяет решить всю задачу целиком за один согласованный проход, а не за $V$ разрозненных.
Определение: Задача о кратчайших путях между всеми парами вершин состоит в том, чтобы для взвешенного ориентированного графа $G=(V,E)$ с $n$ вершинами найти матрицу $D$ размера $n \times n$, где $D[i][j]$ равно весу кратчайшего пути из вершины $i$ в вершину $j$ (или $\infty$, если путь не существует, и $0$, если $i=j$). В отличие от задачи с одним источником, которую решает алгоритм Дейкстры за один запуск, здесь нужны ответы сразу для всех $n^2$ упорядоченных пар вершин.
Примеры с разбором
Пример 1 (лёгкий). Транспортная компания обслуживает $5$ городов. Раньше диспетчер вручную считал маршрут для каждого нового заказа доставки, вызывая поиск кратчайшего пути от точки отправления до точки назначения. Компания хочет заранее построить единую таблицу расстояний между всеми парами городов, чтобы отвечать на запросы клиентов мгновенно. Сформулируй, чем такая задача принципиально отличается от задачи, которую решала бы Дейкстра, если бы диспетчер фиксировал точку отправления заранее.
Если бы точка отправления была заранее известна и фиксирована (например, все заказы всегда идут из главного склада), задача сводилась бы к одному запуску Дейкстры: один источник — все остальные вершины как приёмники, ровно та постановка, которую этот алгоритм и решает эффективнее всего. Но в реальности заказ может прийти с отправкой из любого из $5$ городов в любой другой — то есть источник не фиксирован, диспетчеру заранее не известно, какая из $5 \times 4 = 20$ упорядоченных пар городов понадобится следующей. Чтобы отвечать мгновенно на любой из этих $20$ возможных запросов, нужна не одна цепочка кратчайших путей от одной вершины, а полная матрица $5 \times 5$, где каждая ячейка уже содержит готовый ответ, — именно это и есть задача о кратчайших путях между всеми парами.
Пример 2 (средний). В социальной сети $6$ пользователей связаны отношениями «подписан на» — это ориентированный граф, где ребро $u \to v$ означает, что информация может дойти от $u$ до $v$ за один «шаг» пересылки. Сервис хочет для функции «предложить друзей» знать кратчайшую цепочку связей между КАЖДОЙ парой пользователей, а не только между конкретным пользователем и остальными. Почему здесь также нужна именно задача «всех пар», а не серия отдельных запросов Дейкстры по требованию?
Функция «предложить друзей» работает не для одного заранее известного пользователя, а потенциально для любого из $6$ пользователей в любой момент времени, когда он заходит в приложение — то есть источник запроса каждый раз новый, и заранее неизвестно, для кого именно система будет строить рекомендации следующей. Если бы сервис запускал Дейкстру заново при каждом визите каждого пользователя, это означало бы многократное дублирование вычислений (одна и та же информация о расстояниях между дальними парами пересчитывалась бы снова и снова при каждом визите), да ещё и с задержкой в реальном времени, заметной пользователю. Заранее посчитанная методом Флойда-Уоршелла полная матрица $6 \times 6$ решает эту проблему раз и навсегда: как только структура связей меняется, таблицу пересчитывают один раз (или обновляют инкрементально), а любой запрос «расстояние между X и Y» после этого — это просто чтение одной ячейки готовой таблицы за $O(1)$, без какого-либо нового поиска.
Пример 3 (сложный, полная трассировка). Дан небольшой ориентированный граф из трёх городов — A, B и C — со следующими прямыми дорогами: из A в B — $4$ часа пути, из B в C — $2$ часа, из A в C — $9$ часов (прямая, но длинная дорога в обход). Построй начальную матрицу расстояний и найди истинные кратчайшие расстояния между всеми парами городов, разрешая проезд через промежуточный город.
Начальная матрица $D^{(0)}$ содержит только прямые рёбра, диагональ — нули (расстояние от города до себя), отсутствующие прямые связи — бесконечность:
A B C
A[ 0 4 9]
B[ ∞ 0 2]
C[ ∞ ∞ 0]
Рассмотрим промежуточные города по очереди. Через A как промежуточный город: чтобы куда-то попасть через A, нужен путь, ведущий В A, а таких путей в этом графе нет ни у кого (столбец A состоит из одних бесконечностей, кроме диагонали) — значит на этом шаге ничего не меняется. Через B как промежуточный город: единственная содержательная проверка — путь из A в C через B, то есть $D[A][B] + D[B][C] = 4 + 2 = 6$ часов, что меньше прямой дороги в $9$ часов, — значит $D[A][C]$ обновляется до $6$. Через C как промежуточный город: у C нет исходящих дорог, кроме как в себя, так что проверять больше нечего.
Итоговая матрица:
A B C
A[ 0 4 6]
B[ ∞ 0 2]
C[ ∞ ∞ 0]
Почему это важно. Уже на этом крошечном примере из трёх городов видно главное отличие постановки задачи: даже если тебя интересовало бы только расстояние от A до C, тот же самый проход алгоритма заодно вычислил и расстояние от A до B, и от B до C — все пары получают ответ одновременно, за один согласованный проход по графу, а не за отдельные независимые вычисления. Именно эта особенность делает задачу «всех пар» принципиально другой формулировкой, а не просто «Дейкстрой, повторённой много раз»: здесь с самого начала работают не с одной стартовой вершиной, а сразу со всей матрицей целиком.
Идея динамического программирования и рекуррентная формула
Интуиция: разрешаем себе всё больше промежуточных остановок
Представь, что ты играешь в игру: изначально тебе разрешено строить маршруты между городами, используя ТОЛЬКО прямые дороги — никаких пересадок. Матрица расстояний в этом состоянии — это просто список прямых рёбер графа. Затем правила меняются: тебе разрешают делать одну пересадку, но только через строго определённый город номер $1$. Ты пересчитываешь все расстояния заново с учётом этой новой возможности — некоторые пары городов вдруг оказываются связаны более коротким путём через город $1$, чем напрямую. Затем правила меняются снова: теперь можно пересаживаться через город $1$ ИЛИ через город $2$ (или через оба сразу, в любом порядке). Снова пересчитываешь. И так далее, пока не откроешь возможность пересадки через любой из $n$ городов графа — в этот момент матрица расстояний становится окончательной и совпадает с истинными кратчайшими расстояниями по всему графу.
Это и есть идея динамического программирования, на которой построен алгоритм Флойда-Уоршелла: вместо того чтобы пытаться решить задачу «найти кратчайший путь с любым числом промежуточных вершин» напролом, задачу разбивают на последовательность из $n$ более простых подзадач, каждая из которых спрашивает «а что если разрешить путям проходить только через первые $k$ вершин графа в качестве промежуточных остановок». При $k=0$ подзадача тривиальна — это просто исходные веса прямых рёбер. При $k=n$ подзадача совпадает с исходной задачей целиком. Переход от подзадачи с $k-1$ разрешённой промежуточной вершиной к подзадаче с $k$ разрешёнными — это один простой вопрос для каждой пары $(i,j)$: выгодно ли теперь, когда вершина $k$ стала доступна как промежуточная остановка, пройти через неё, или лучше оставить путь таким же, каким он был без неё?
Рекуррентная формула: Обозначим через $D^{(k)}[i][j]$ длину кратчайшего пути из $i$ в $j$, при котором в качестве промежуточных вершин разрешено использовать только вершины из множества $\{1, 2, \dots, k\}$. Тогда
$$D^{(k)}[i][j] = \min\Big(D^{(k-1)}[i][j],\ D^{(k-1)}[i][k] + D^{(k-1)}[k][j]\Big),$$где первое слагаемое — «не используем вершину $k$ вообще», второе — «проходим через вершину $k$ ровно один раз». Базовый случай: $D^{(0)}[i][j]$ равно весу прямого ребра $(i,j)$, если оно существует, $0$ при $i=j$, и $\infty$ иначе. Ответом на исходную задачу служит $D^{(n)}$.
Практическая деталь, которая на первый взгляд выглядит как трюк, но на самом деле строго обоснована: реализовывать трёхмерный массив $D^{(k)}[i][j]$ по индексу $k$ не нужно — достаточно одной двумерной матрицы, которую алгоритм обновляет «на месте» при переходе от одного $k$ к следующему. Это работает, потому что значения $D[i][k]$ и $D[k][j]$, используемые в формуле, за текущую итерацию по $k$ не меняются: путь из $i$ в $k$, использующий сам $k$ в качестве промежуточной вершины, не может быть короче пути, использующего вершины только до $k-1$ (потому что зайти в $k$, чтобы затем снова использовать $k$, не даёт выигрыша при неотрицательном цикле, а сама идея опирается на то, что $D[i][k]$ и $D[k][j]$ на шаге $k$ уже финальны). Именно поэтому классическая реализация укладывается в три простых вложенных цикла:
def floyd_warshall(dist):
n = len(dist)
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Временная сложность такого решения — $O(n^3)$, поскольку три вложенных цикла проходят по $n$ значений каждый; пространственная сложность — $O(n^2)$ на хранение самой матрицы расстояний (без учёта дополнительной матрицы предков, если нужно восстанавливать сами пути, а не только их длины).
Примеры с разбором
Пример 1 (лёгкий). Даны текущие значения $D[i][j] = 7$, $D[i][k] = 3$, $D[k][j] = 2$. Примени рекуррентную формулу и найди новое значение $D[i][j]$.
По формуле $D[i][j] = \min(D[i][j],\ D[i][k]+D[k][j])$. Путь через $k$ имеет длину $3+2=5$. Сравниваем с текущим значением $7$: $\min(7, 5) = 5$. Путь через $k$ оказался короче прямого — новое значение $D[i][j] = 5$.
Пример 2 (средний). Даны значения $D[i][j] = \infty$ (прямого пути нет), $D[i][k] = 6$, $D[k][j] = \infty$ (через $k$ тоже нельзя дойти до $j$ напрямую). Что произойдёт при применении формулы, и почему важно, что при этом не возникает ошибки переполнения?
$D[i][k] + D[k][j] = 6 + \infty = \infty$, значит $\min(\infty, \infty) = \infty$ — значение не меняется. Это важный технический момент: складывать «бесконечность» с конечным числом безопасно, если бесконечность действительно представлена достаточно большим значением (или специальным символом float('inf') в языках с плавающей точкой), но если недостижимость закодировать, например, обычным большим целым числом вроде $10^9$, а граф содержит несколько последовательных недостижимых переходов, сумма двух таких «псевдобесконечностей» может переполнить используемый тип данных или, что хуже, стать меньше настоящего кратчайшего пути и незаметно исказить результат — поэтому на практике либо используют настоящую бесконечность с плавающей точкой, либо явно проверяют условие if dist[i][k] < INF and dist[k][j] < INF перед суммированием.
Пример 3 (сложный, полная трассировка). Дана сеть дорог между четырьмя городами — Уфа (0), Казань (1), Самара (2), Пенза (3) — с прямыми дорогами: Уфа → Казань — $5$ часов, Уфа → Пенза — $10$ часов, Казань → Самара — $3$ часа, Самара → Пенза — $1$ час. Проследи все четыре итерации алгоритма ($k=0,1,2,3$) и найди итоговую матрицу кратчайших расстояний.
Начальная матрица:
0 1 2 3
0[ 0 5 ∞ 10]
1[ ∞ 0 3 ∞]
2[ ∞ ∞ 0 1]
3[ ∞ ∞ ∞ 0]
Итерация $k=0$ (Уфа как промежуточный город). В Уфу не ведёт ни одна дорога (весь столбец $0$, кроме диагонали, — бесконечность), значит любой путь «через Уфу» использует бесконечность и не может улучшить ничего. Матрица не меняется.
Итерация $k=1$ (Казань как промежуточный город). Проверяем все пары. Единственное содержательное улучшение: $D[0][2] = \min(\infty,\ D[0][1]+D[1][2]) = \min(\infty,\ 5+3) = 8$ — путь Уфа → Казань → Самара короче, чем полное отсутствие прямой дороги. Остальные пары либо не затрагивают Казань как промежуточную точку с выгодой, либо упираются в бесконечность (в Казань, кроме как из Уфы, ничего не ведёт). Матрица после этой итерации:
0 1 2 3
0[ 0 5 8 10]
1[ ∞ 0 3 ∞]
2[ ∞ ∞ 0 1]
3[ ∞ ∞ ∞ 0]
Итерация $k=2$ (Самара как промежуточный город). Проверяем: $D[0][3] = \min(10,\ D[0][2]+D[2][3]) = \min(10,\ 8+1) = 9$ — путь Уфа → Казань → Самара → Пенза длиной $9$ часов оказался короче прямой дороги в $10$ часов. Также $D[1][3] = \min(\infty,\ D[1][2]+D[2][3]) = \min(\infty,\ 3+1) = 4$ — раньше из Казани в Пензу вообще не было известного пути, теперь появился через Самару. Матрица:
0 1 2 3
0[ 0 5 8 9]
1[ ∞ 0 3 4]
2[ ∞ ∞ 0 1]
3[ ∞ ∞ ∞ 0]
Итерация $k=3$ (Пенза как промежуточный город). Из Пензы никуда, кроме себя, дорог нет — значит проверять нечего, матрица остаётся без изменений и становится финальной.
Почему это важно. На этой трассировке видно главное свойство рекурсии: на каждом шаге пересчитывается сразу вся матрица целиком, а не путь от одной конкретной вершины — уже к итерации $k=2$ у нас появились правильные кратчайшие расстояния сразу для нескольких независимых пар (и от Уфы, и от Казани до Пензы), потому что обе пары выиграли от одной и той же вновь открывшейся промежуточной вершины. Именно эта возможность «одним обновлением улучшить сразу много пар» и объясняет, почему алгоритм эффективнее, чем перебор путей для каждой пары вершин по отдельности.
Отрицательные веса рёбер и обнаружение отрицательного цикла
Интуиция: почему жадность Дейкстры ломается, а динамическое программирование — нет
Алгоритм Дейкстры устроен жадно: на каждом шаге он окончательно фиксирует кратчайшее расстояние до вершины с наименьшей текущей меткой, полагая, что раз эта метка минимальна среди ещё не обработанных вершин, короче она уже стать не может. Это предположение опирается на то, что все веса рёбер неотрицательны — тогда любой дальнейший путь может только увеличивать длину, никогда не уменьшать её задним числом. Но стоит появиться в графе хотя бы одному отрицательному ребру, и это предположение рушится: может обнаружиться более короткий путь до уже «окончательно» обработанной вершины именно через отрицательное ребро, но Дейкстра к этому моменту уже закрыла эту вершину и пересматривать её не станет.
Флойд-Уоршелл этой ловушки избегает в принципе, потому что не делает никаких жадных «окончательных» решений по ходу работы: он попросту перебирает все возможные промежуточные вершины по очереди и на каждом шаге берёт минимум из двух явно сравниваемых вариантов, не полагаясь на предположение о неотрицательности весов нигде в самой логике сравнения. Формула $\min(D[i][j],\ D[i][k]+D[k][j])$ одинаково корректна и для положительных, и для отрицательных чисел — минимум есть минимум. Именно поэтому Флойд-Уоршелл спокойно работает с отрицательными весами рёбер там, где Дейкстра дала бы неверный ответ.
Но есть принципиальная граница, которую не может перейти ни один алгоритм кратчайших путей, включая Флойд-Уоршелл: если в графе есть цикл, суммарный вес рёбер которого отрицателен, — понятие «кратчайший путь» между вершинами, через которые проходит этот цикл, перестаёт иметь смысл. Пройдя по такому циклу один раз, ты уменьшаешь длину маршрута; пройдя дважды — уменьшаешь ещё; и так можно продолжать бесконечно, устремляя длину «кратчайшего» пути к минус бесконечности. Хорошая новость в том, что тот же самый алгоритм, без единой дополнительной строчки логики, сам сигнализирует о существовании такого цикла: если после выполнения всех $n$ итераций диагональный элемент $D[i][i]$ для какой-то вершины $i$ оказался отрицательным, значит существует путь из $i$ обратно в $i$ с отрицательным суммарным весом — то есть отрицательный цикл, проходящий через $i$.
Правило проверки: После завершения алгоритма Флойда-Уоршелла пройди по диагонали итоговой матрицы. Если хотя бы для одного $i$ выполняется $D[i][i] < 0$, граф содержит отрицательный цикл, и все расстояния, вычисленные для вершин, достижимых из этого цикла и способных достичь его обратно, не имеют смысла как «кратчайшие пути» — они лишь показывают, что путь можно сделать сколь угодно коротким.
Примеры с разбором
Пример 1 (лёгкий). Дан цикл из трёх рёбер: $A \to B$ весом $2$, $B \to C$ весом $-5$, $C \to A$ весом $1$. Посчитай суммарный вес цикла и определи, является ли он отрицательным.
Суммарный вес: $2 + (-5) + 1 = -2$. Поскольку сумма отрицательна, это отрицательный цикл — двигаясь по кругу $A \to B \to C \to A$ снова и снова, суммарная «длина» пути становится всё меньше и меньше без ограничения, поэтому корректного кратчайшего пути между вершинами этого цикла не существует.
Пример 2 (средний, полная трассировка без цикла). Дан граф с тремя вершинами X, Y, Z и рёбрами: $X \to Y$ весом $4$, $Y \to Z$ весом $-6$, $X \to Z$ весом $5$ (циклов в графе нет — рёбра идут только «вперёд»). Найди итоговую матрицу кратчайших расстояний и убедись, что отрицательное ребро корректно учтено.
Начальная матрица:
X Y Z
X[ 0 4 5]
Y[ ∞ 0 -6]
Z[ ∞ ∞ 0]
Итерация $k=X$: в X не ведёт ни одна дорога — без изменений. Итерация $k=Y$: проверяем $D[X][Z] = \min(5,\ D[X][Y]+D[Y][Z]) = \min(5,\ 4+(-6)) = \min(5,\ -2) = -2$ — путь через Y с учётом отрицательного ребра оказался короче прямого. Итерация $k=Z$: из Z дорог, кроме как в себя, нет — без изменений.
Итоговая матрица:
X Y Z
X[ 0 4 -2]
Y[ ∞ 0 -6]
Z[ ∞ ∞ 0]
Обрати внимание: если бы к этому графу применили Дейкстру из X, она бы на первом шаге закрыла вершину Z как «уже достигнутую» кратчайшим образом с расстоянием $5$ (прямое ребро), поскольку на тот момент это наименьшая известная метка — и не стала бы пересматривать это решение, даже когда впоследствии через Y открылся бы путь длиной $-2$. Именно так и проявляется поломка жадного предположения Дейкстры при появлении отрицательных весов.
Пример 3 (сложный, полная трассировка обнаружения отрицательного цикла). Дан граф с тремя вершинами P, Q, R и рёбрами: $P \to Q$ весом $1$, $Q \to R$ весом $-3$, $R \to P$ весом $1$. Суммарный вес цикла $P \to Q \to R \to P$ равен $1+(-3)+1=-1$ — это отрицательный цикл. Проследи, как алгоритм обнаруживает это через диагональ итоговой матрицы.
Начальная матрица:
P Q R
P[ 0 1 ∞]
Q[ ∞ 0 -3]
R[ 1 ∞ 0]
Итерация $k=P$: обновляем через столбец и строку P. Единственное значимое изменение — $D[R][Q] = \min(\infty,\ D[R][P]+D[P][Q]) = \min(\infty,\ 1+1) = 2$.
P Q R
P[ 0 1 ∞]
Q[ ∞ 0 -3]
R[ 1 2 0]
Итерация $k=Q$: $D[P][R] = \min(\infty,\ D[P][Q]+D[Q][R]) = \min(\infty,\ 1+(-3)) = -2$. И важнее всего: $D[R][R] = \min(0,\ D[R][Q]+D[Q][R]) = \min(0,\ 2+(-3)) = \min(0,-1) = -1$ — диагональный элемент впервые становится отрицательным!
P Q R
P[ 0 1 -2]
Q[ ∞ 0 -3]
R[ 1 2 -1]
Итерация $k=R$: обновляем через столбец и строку R. В частности, $D[P][P] = \min(0,\ D[P][R]+D[R][P]) = \min(0,\ -2+1) = -1$, $D[Q][Q] = \min(0,\ D[Q][R]+D[R][Q]) = \min(0,\ -3+2) = -1$, и $D[R][R] = \min(-1,\ D[R][R]+D[R][R]) = \min(-1,\ -1+(-1)) = -2$.
P Q R
P[ -1 0 -3]
Q[ -2 -1 -4]
R[ 0 1 -2]
Все три диагональных элемента — $D[P][P]=-1$, $D[Q][Q]=-1$, $D[R][R]=-2$ — отрицательны. Это однозначный сигнал: через каждую из вершин P, Q, R проходит отрицательный цикл (что логично: все три вершины лежат на одном и том же цикле $P \to Q \to R \to P$), и значения расстояний в этой матрице больше не являются корректными кратчайшими путями — при дальнейших повторных прогонах алгоритма они продолжили бы уменьшаться без предела.
Почему это важно. На практике проверка диагонали после выполнения алгоритма — это не факультативная предосторожность, а обязательный финальный шаг всегда, когда в графе теоретически могут быть отрицательные веса: пропустить эту проверку — значит рискнуть тихо выдать пользователю или следующему этапу пайплайна бессмысленные, искусственно заниженные «расстояния», которые выглядят как валидные числа, но таковыми не являются. Ровно эта же техника — обнаружение отрицательного цикла как сигнала о существовании выгодного кругового обмена — лежит в основе алгоритмов поиска арбитража на валютных и товарных рынках, к чему мы ещё вернёмся в разделе с практикой.
Сравнение с многократным запуском Дейкстры
Интуиция: один универсальный молоток против набора специализированных инструментов
На первый взгляд кажется, что раз Дейкстра решает задачу с одним источником эффективно, то для задачи «все пары» достаточно просто вызвать её $V$ раз — по одному разу для каждой вершины в роли источника. Это абсолютно корректное решение, и часто оно даже быстрее Флойда-Уоршелла — но справедливо это далеко не всегда, и понимание того, от чего зависит победитель этого сравнения, — важная часть практической грамотности при работе с графами.
Ключевая переменная в этом сравнении — плотность графа, то есть соотношение числа рёбер $E$ и числа вершин $V$. Алгоритм Дейкстры с бинарной кучей имеет сложность $O((E+V)\log V)$ на один запуск; если запустить его из каждой из $V$ вершин, суммарная сложность составит $O(V(E+V)\log V)$. Для разреженного графа, где $E$ растёт линейно с $V$ (типичная ситуация для дорожных сетей, где у каждого перекрёстка лишь несколько соседей), эта величина оказывается заметно меньше, чем $O(V^3)$ Флойда-Уоршелла — и тогда многократный запуск Дейкстры выигрывает. Но для плотного графа, где $E$ приближается к $V^2$ (например, полный граф всех попарных расстояний между точками на карте без ограничений связности), множитель $E$ внутри $O(V(E+V)\log V)$ сам приближается к $V^2$, и вся конструкция превращается в $O(V^3 \log V)$ — что уже хуже, чем чистый $O(V^3)$ Флойда-Уоршелла, из-за лишнего логарифмического множителя.
Второе решающее отличие — работа с отрицательными весами. Если в графе есть отрицательные рёбра (но нет отрицательных циклов), классическая Дейкстра неприменима вообще, ни разу, независимо от плотности графа, — она в принципе даёт неверный ответ на графах с отрицательными весами, как было показано в предыдущем разделе. В такой ситуации единственный корректный выбор из рассмотренных — это либо Флойд-Уоршелл, либо более специализированная комбинация: алгоритм Беллмана-Форда (который умеет работать с отрицательными весами и даже обнаруживает отрицательные циклы, но решает задачу только с одним источником, за $O(VE)$) плюс приём под названием «перевзвешивание», формирующий основу алгоритма Джонсона — трёхэтапной процедуры, которая сначала запускает Беллмана-Форда один раз, чтобы избавиться от отрицательных весов с помощью математического трюка, а затем запускает уже обычную, быструю Дейкстру $V$ раз на исправленном графе. Для разреженных графов с отрицательными весами (но без отрицательных циклов) алгоритм Джонсона со сложностью $O(V^2\log V + VE)$ асимптотически превосходит $O(V^3)$ Флойда-Уоршелла, но он значительно сложнее в реализации и понимании — а Флойд-Уоршелл остаётся простым и надёжным выбором «по умолчанию», особенно когда граф некрупный или когда важна именно простота и предсказуемость кода, а не выжимание последних процентов производительности.
Практическое правило выбора: Для маленьких и средних плотных графов (скажем, до нескольких сотен вершин) или при наличии отрицательных весов без сложных требований к производительности — Флойд-Уоршелл: три строчки кода, никаких вспомогательных структур, простая проверка отрицательных циклов. Для больших разреженных графов с неотрицательными весами — многократный запуск Дейкстры. Для больших разреженных графов с отрицательными весами (без отрицательных циклов) — алгоритм Джонсона.
Примеры с разбором
Пример 1 (лёгкий, полная трассировка). Дан граф из трёх серверов дата-центра — S1, S2, S3 — с задержками передачи данных: $S1 \to S2 = 2$ мс, $S2 \to S3 = 2$ мс, $S1 \to S3 = 10$ мс (прямой, но перегруженный канал). Построй итоговую матрицу задержек методом Флойда-Уоршелла и сравни результат с тем, что дали бы три отдельных запуска Дейкстры.
Начальная матрица:
S1 S2 S3
S1[ 0 2 10]
S2[ ∞ 0 2]
S3[ ∞ ∞ 0]
Итерация $k=S1$: без изменений (в S1 ничего не ведёт). Итерация $k=S2$: $D[S1][S3] = \min(10,\ 2+2) = 4$. Итерация $k=S3$: без изменений (из S3 дорог нет).
Итоговая матрица:
S1 S2 S3
S1[ 0 2 4]
S2[ ∞ 0 2]
S3[ ∞ ∞ 0]
Три отдельных запуска Дейкстры (из S1, из S2, из S3) на этом же графе дали бы в точности те же самые числа — оба подхода корректны для графа без отрицательных весов. Разница не в результате, а в процессе: Флойд-Уоршелл получил все девять значений матрицы за один согласованный проход, тогда как три запуска Дейкстры потребовали бы трижды заново обходить граф и трижды строить (пусть маленькую) очередь с приоритетом.
Пример 2 (средний). Граф дорожной сети из $100$ вершин представляет собой типичную городскую сеть, где у каждого перекрёстка в среднем $4$ соседних, то есть $E \approx 100 \cdot 4 / 2 = 200$ рёбер (разреженный граф). Оцени порядок числа операций для Флойда-Уоршелла и для стократного запуска Дейкстры с бинарной кучей, и определи, какой подход эффективнее.
Флойд-Уоршелл: $O(V^3) = 100^3 = 1\,000\,000$ операций. Многократная Дейкстра: $O(V(E+V)\log V) = 100 \cdot (200+100) \cdot \log_2(100) \approx 100 \cdot 300 \cdot 6{,}64 \approx 199\,200$ операций. Разреженность резко меняет картину: многократный запуск Дейкстры выполняет примерно в $5$ раз меньше операций, чем Флойд-Уоршелл, — для такого разреженного графа она оказывается заметно эффективнее.
Пример 3 (сложный). Тот же город с $100$ перекрёстками теперь рассматривается как гипотетически «полностью связанный» граф — между каждой парой перекрёстков напрямую известно расстояние (например, это уже не дорожная сеть, а матрица расстояний по прямой между точками интереса на карте), то есть $E \approx V^2/2 = 5000$. Пересчитай оценки для обоих подходов и объясни, как поменялся победитель сравнения.
Флойд-Уоршелл по-прежнему $O(V^3) = 1\,000\,000$ операций — эта оценка не зависит от плотности графа вообще, так как алгоритм всегда перебирает все $n^3$ троек индексов. Многократная Дейкстра теперь: $O(V(E+V)\log V) = 100 \cdot (5000+100) \cdot \log_2(100) \approx 100 \cdot 5100 \cdot 6{,}64 \approx 3\,386\,400$ операций — почти в $3{,}4$ раза больше, чем у Флойда-Уоршелла. Плотность графа развернула сравнение на противоположное: для разреженного графа выгоднее была многократная Дейкстра, а для плотного — Флойд-Уоршелл, потому что его сложность не зависит от числа рёбер вообще, тогда как сложность Дейкстры растёт вместе с $E$.
Почему это важно. Выбор алгоритма «по умолчанию» без анализа плотности графа и наличия отрицательных весов — частая практическая ошибка: на собеседовании или в учебнике Флойд-Уоршелл заслуженно популярен из-за простоты реализации, но бездумное применение его к разреженному графу из миллиона вершин закончится реальной катастрофой производительности ($10^{18}$ операций просто не выполнить за разумное время), тогда как для плотного графа из сотни вершин с отрицательными весами именно Флойд-Уоршелл окажется и самым быстрым, и самым простым в реализации решением одновременно.
Практика: 30 заданий
Базовые (задания 1–10)
Задание 1. Дан ориентированный граф из трёх вершин с рёбрами: $1 \to 2$ весом $3$, $2 \to 3$ весом $4$, $1 \to 3$ весом $8$. Построй начальную матрицу расстояний $D^{(0)}$.
Задание 2. Известно, что $D[i][j]=5$, $D[i][k]=2$, $D[k][j]=2$. Примени рекуррентную формулу Флойда-Уоршелла и найди обновлённое значение $D[i][j]$.
Задание 3. Известно, что $D[i][j]=\infty$, $D[i][k]=3$, $D[k][j]=4$. Примени рекуррентную формулу и найди обновлённое значение $D[i][j]$.
Задание 4. Для графа из задания 1 выполни только итерацию $k=1$ (промежуточная вершина — вершина $1$) и укажи, изменится ли матрица.
Задание 5. Для графа из $V=50$ вершин определи временную сложность алгоритма Флойда-Уоршелла в виде конкретного числа элементарных операций и требуемый объём памяти под матрицу расстояний (в числе ячеек).
Задание 6. Дан граф с ребром $A \to B$ весом $-4$ и рёбрами $B \to C$ весом $6$, $C \to A$ весом $1$. Проверь, является ли цикл $A \to B \to C \to A$ отрицательным, и можно ли в этом графе безопасно применять Флойд-Уоршелл.
Задание 7. Укажи правильный порядок вложенности трёх циклов в классической реализации Флойда-Уоршелла и объясни, какой цикл обязан быть внешним.
Задание 8. После выполнения алгоритма Флойда-Уоршелла на некотором графе диагональный элемент $D[2][2] = -3$. Что это означает?
Задание 9. Граф содержит $V=10$ вершин и $E=20$ рёбер. Сравни число операций Флойда-Уоршелла ($V^3$) и десяти запусков Дейкстры с бинарной кучей (используй оценку $V \cdot (E+V) \cdot \log_2 V$ на все запуски).
Задание 10. Дан граф из трёх вершин P, Q, R с рёбрами $P \to Q = 6$, $Q \to R = 3$, $P \to R = 20$. Найди кратчайшие расстояния между всеми парами методом Флойда-Уоршелла.
Средние (задания 11–20)
Задание 11. Дан граф из четырёх вершин $1,2,3,4$ с рёбрами: $1\to2=2$, $1\to4=9$, $2\to3=4$, $3\to4=2$. Выполни полную трассировку алгоритма (все четыре итерации) и найди итоговую матрицу.
Задание 12. Опиши, как для восстановления не только длины, но и самого маршрута кратчайшего пути нужно модифицировать алгоритм — какую дополнительную структуру данных нужно вести параллельно с матрицей расстояний.
Задание 13. Логистическая сеть из четырёх складов A, B, C, D имеет маршруты: $A\to B=7$, $B\to D=3$, $A\to C=2$, $C\to D=4$. Найди кратчайший маршрут доставки из A в D и укажи, через какой склад он проходит.
Задание 14. Три валюты — USD, EUR, RUB — со следующими курсами обмена: USD→EUR = $0{,}9$, EUR→RUB = $90$, RUB→USD = $0{,}012$. Определи, есть ли выгодный цикл арбитража (прокрути $1$ доллар по циклу и посчитай итоговую сумму).
Задание 15. Для графа из $V=1000$ вершин посчитай, сколько ячеек памяти потребуется под матрицу расстояний, и оцени, сколько мегабайт это займёт, если каждое число хранится в виде $8$-байтового значения с плавающей точкой.
Задание 16. Для графа с $V=100$ вершинами сравни оценку числа операций Флойда-Уоршелла и многократной Дейкстры (формула $V\cdot(E+V)\cdot\log_2 V$) для двух случаев: разреженного графа ($E\approx100$) и плотного графа ($E\approx5000$).
Задание 17. Модифицируй рекуррентную формулу Флойда-Уоршелла для решения задачи транзитивного замыкания: булева матрица $R[i][j]$ показывает, достижима ли вершина $j$ из вершины $i$ хоть каким-то путём (без учёта весов). Дан граф $A\to B$, $B\to C$ (нет прямого ребра $A\to C$). Примени модифицированную формулу и определи $R[A][C]$ после рассмотрения промежуточной вершины B.
Задание 18. В сети из $4$ пользователей социальной сети известны прямые связи «подписан на»: $1\to2$, $2\to3$, $3\to4$, $4\to1$ (все длиной $1$). Найди степень разделения (кратчайшее число «шагов») между пользователем $1$ и пользователем $3$.
Задание 19. Объясни на содержательном уровне, почему при неправильной реализации, где цикл по $i$ поставлен внешним, а цикл по $k$ — внутренним, результат может оказаться неверным, даже если формула обновления записана правильно.
Задание 20. Для графа из $V=200$ вершин посчитай точное число выполнений внутреннего тела тройного цикла алгоритма Флойда-Уоршелла.
Сложные (задания 21–30)
Задание 21. Дан граф из трёх вершин D, E, F с отрицательными весами (без цикла): $D\to E = 6$, $E\to F = -8$, $D\to F = 5$. Выполни полную трассировку и найди итоговую матрицу.
Задание 22. Дан цикл из трёх вершин M, N, O с рёбрами $M\to N=2$, $N\to O=-5$, $O\to M=1$. Проверь, является ли цикл отрицательным, и если да — укажи, какие диагональные элементы итоговой матрицы станут отрицательными.
Задание 23. Используя матрицу $next[i][j]$ из задания 12, известно: $next[A][D] = C$, $next[C][D] = D$. Восстанови полный кратчайший маршрут из A в D.
Задание 24. Разреженный граф из $V=2000$ вершин и $E=6000$ рёбер содержит отрицательные веса, но не содержит отрицательных циклов. Сравни целесообразность применения Флойда-Уоршелла ($V^3$) и алгоритма Джонсона (оценка сложности $V^2\log V + VE$).
Задание 25. Редакционное расстояние Левенштейна между двумя строками вычисляется через рекуррентную формулу динамического программирования, где ячейка $L[i][j]$ (минимальное число правок для первых $i$ и $j$ символов строк) вычисляется как минимум из трёх вариантов перехода (вставка, удаление, замена символа). Объясни, что именно объединяет эту схему с рекуррентной формулой Флойда-Уоршелла на уровне общей идеи.
Задание 26. В сетевом анализе центральность по близости узла $v$ определяется как величина, обратная сумме кратчайших расстояний от $v$ до всех остальных узлов графа. Дана итоговая матрица расстояний для графа из $4$ узлов, где сумма расстояний от узла $2$ до остальных трёх узлов равна $6$, а от узла $4$ — равна $15$. У какого узла центральность по близости выше и почему это требует именно полной матрицы всех попарных расстояний?
Задание 27. Стриминговый сервис имеет серверы в трёх городах: Москва, Берлин, Токио, с задержками передачи данных $M\to B=40$ мс, $B\to T=180$ мс, $M\to T=250$ мс (прямой, но медленный канал). Найди оптимальный маршрут маршрутизации трафика из Москвы в Токио.
Задание 28. Четыре валюты: USD, EUR, GBP, JPY с курсами обмена USD→EUR = $0{,}95$, EUR→GBP = $0{,}87$, GBP→JPY = $190$, JPY→USD = $0{,}0068$. Используя переход к весам $-\ln(\text{курс})$, определи, существует ли в этом цикле выгодный арбитраж.
Задание 29. Для графа из $V=10\,000$ вершин оцени, сколько операций потребует Флойд-Уоршелл, и, предположив, что современный процессор выполняет примерно $10^9$ таких операций в секунду, оцени время выполнения.
Задание 30. Дан граф маршрутов авиакомпании между городами, где часть рёбер представляет не расстояние, а «стоимость с учётом бонусной программы» (может быть отрицательной для акционных маршрутов). После выполнения Флойда-Уоршелла обнаружено, что $D[X][X] = -12$ для города X. Опиши, что это означает и как стоит поступить дальше.
Частые ошибки
❌ Ошибка: Ставить цикл по $k$ не самым внешним из трёх вложенных циклов ✅ Правильно: Цикл по $k$ (промежуточная вершина) обязан быть внешним, циклы по $i$ и $j$ — вложенными в него 💡 Почему: Корректность рекуррентной формулы опирается на то, что значения $D[i][k]$ и $D[k][j]$ уже полностью финализированы к моменту их использования как «моста» — это гарантируется только строгим порядком обработки промежуточных вершин по возрастанию, как показано в задании 19.
❌ Ошибка: Применять алгоритм Дейкстры к графу с отрицательными весами рёбер, полагая, что он просто даст «немного неточный», но приемлемый результат ✅ Правильно: Дейкстра на графе с отрицательными весами может дать результат, произвольно далёкий от истинного кратчайшего пути — жадное предположение о неотрицательности весов ломается полностью, а не частично 💡 Почему: Как показано в разделе про отрицательные веса, Дейкстра «закрывает» вершину как окончательно обработанную сразу после того, как она получает наименьшую текущую метку среди необработанных, и никогда не пересматривает уже закрытые вершины — при отрицательных рёбрах более короткий путь может открыться уже после закрытия вершины.
❌ Ошибка: Не проверять диагональ итоговой матрицы на наличие отрицательных значений, если граф потенциально мог содержать отрицательные веса ✅ Правильно: Всегда проверяй $D[i][i]$ для всех $i$ после выполнения алгоритма, если в графе в принципе могли встретиться отрицательные рёбра 💡 Почему: Без этой проверки алгоритм молча вернёт формально валидно выглядящую, но бессмысленную матрицу расстояний, если в графе есть отрицательный цикл — числа будут казаться обычными результатами, хотя реального кратчайшего пути между затронутыми вершинами не существует.
❌ Ошибка: Использовать обычное большое целое число (например, $10^9$) вместо настоящей бесконечности для кодирования недостижимости, не проверяя переполнение при суммировании
✅ Правильно: Используй float('inf') (или аналог в своём языке программирования) либо явно проверяй условие «оба слагаемых меньше псевдобесконечности» перед сложением
💡 Почему: Как отмечено в задании 3 раздела про рекуррентную формулу, сумма двух больших «псевдобесконечностей» может переполнить тип данных или, что хуже, дать значение меньше реального кратчайшего пути, незаметно исказив результат работы алгоритма.
❌ Ошибка: Применять Флойд-Уоршелл к большому разреженному графу «по умолчанию», не сравнив сложность с многократным запуском Дейкстры или алгоритмом Джонсона ✅ Правильно: Сложность $O(V^3)$ Флойда-Уоршелла не зависит от числа рёбер — для разреженных графов из тысяч и более вершин это почти всегда хуже, чем альтернативы, учитывающие реальную плотность графа 💡 Почему: Как показано в заданиях 16 и 24, разница в числе операций между подходами может достигать сотен раз для достаточно крупных и разреженных графов — выбор алгоритма без оглядки на плотность графа способен превратить решаемую задачу в практически невыполнимую по времени.
❌ Ошибка: Считать, что наличие ОТРИЦАТЕЛЬНОГО ВЕСА ребра автоматически означает наличие отрицательного цикла и делает граф «неправильным» ✅ Правильно: Отдельные отрицательные веса рёбер — совершенно нормальная и корректно обрабатываемая ситуация; проблему представляет только отрицательный ЦИКЛ, то есть замкнутый маршрут с отрицательной суммой весов 💡 Почему: Как показано в примерах с графами X-Y-Z и заданиях 6 и 21, граф с отрицательными рёбрами, но без циклов, обрабатывается алгоритмом абсолютно корректно и даёт валидные, осмысленные кратчайшие расстояния.
Главное запомнить
✅ Флойд-Уоршелл решает задачу кратчайших путей между ВСЕМИ парами вершин за один согласованный проход, в отличие от Дейкстры, которая решает задачу только для одного источника
✅ В основе алгоритма лежит динамическое программирование: множество разрешённых промежуточных вершин расширяется постепенно, от $0$ до $n$, а рекуррентная формула $D[i][j] = \min(D[i][j],\ D[i][k]+D[k][j])$ пересчитывает всю матрицу на каждом шаге
✅ Реализация укладывается в три вложенных цикла, где внешним обязан быть цикл по $k$ (промежуточная вершина) — иначе значения, используемые в формуле, окажутся ещё не финализированными
✅ Временная сложность — $O(V^3)$, пространственная — $O(V^2)$; сложность не зависит от числа рёбер графа
✅ Алгоритм корректно работает с отрицательными весами отдельных рёбер, потому что не полагается на жадное «окончательное» решение, в отличие от Дейкстры
✅ Отрицательный ЦИКЛ (в отличие от отдельного отрицательного ребра) делает понятие «кратчайший путь» некорректным для затронутых вершин — обнаруживается проверкой диагонали итоговой матрицы на наличие отрицательных значений
✅ Для восстановления не только длины, но и самого маршрута нужна дополнительная матрица $next[i][j]$, обновляемая параллельно с матрицей расстояний
✅ Для больших разреженных графов без отрицательных весов эффективнее многократный запуск Дейкстры; для больших разреженных графов с отрицательными весами (без отрицательных циклов) — алгоритм Джонсона; Флойд-Уоршелл выигрывает на небольших и плотных графах, а также там, где важнее простота реализации
✅ Та же рекуррентная схема динамического программирования лежит в основе редакционного расстояния Левенштейна и других задач выравнивания последовательностей
✅ Полная матрица попарных расстояний — необходимый строительный блок для метрик центральности узлов (например, центральности по близости) в сетевом анализе
Связь с другими темами курса
🔙 Откуда пришли: Из урока 263 — алгоритм Дейкстры и задача кратчайшего пути с одним источником, которая служит прямой точкой сравнения для понимания, чем задача «всех пар» принципиально шире; из более ранних уроков о графах — базовые понятия представления графов и обхода
🔜 Куда идём:
- Минимальное остовное дерево (урок 265) — следующая классическая задача на взвешенных графах, но с принципиально другой постановкой: не кратчайшие пути, а минимальное по суммарному весу связное подмножество рёбер
- Более специализированные алгоритмы для больших графов с отрицательными весами — алгоритм Беллмана-Форда и построенный на его основе алгоритм Джонсона
- Продвинутые задачи сетевого анализа, где матрица всех попарных расстояний становится входными данными для вычисления метрик центральности и структуры сообществ
🎯 В машинном обучении и анализе данных: Идея динамического программирования, лежащая в основе Флойда-Уоршелла, — та же парадигма, что используется в алгоритмах выравнивания последовательностей в биоинформатике (сравнение цепочек ДНК и белков) и в обработке естественного языка (редакционное расстояние Левенштейна между строками, лежащее в основе проверки орфографии и нечёткого поиска). Полная матрица попарных кратчайших расстояний применяется в анализе структуры больших графов — например, для вычисления центральности узлов в социальных сетях, графах знаний и рекомендательных системах, а обнаружение отрицательных циклов лежит в основе алгоритмов поиска арбитража на финансовых рынках.
Интересные факты
📌 Алгоритм независимо переоткрывали как минимум трижды за четыре года: Бернар Рой в 1959 году, Роберт Флойд и Стивен Уоршелл — оба в 1962 году, причём решая формально разные задачи (кратчайшие пути и транзитивное замыкание), но пользуясь идентичной рекуррентной схемой.
📌 Роберт Флойд получил премию Тьюринга в 1978 году — не за этот конкретный алгоритм, а за вклад в методологию создания надёжного программного обеспечения в целом; помимо алгоритма кратчайших путей его имя носят ещё как минимум два широко известных алгоритма — обнаружение цикла в связном списке («черепаха и заяц») и построение кучи за линейное время.
📌 Исходная задача Стивена Уоршелла — транзитивное замыкание булевой матрицы — не имела никакого отношения к весам рёбер вообще: он отвечал только на вопрос «да или нет», и лишь позже стало понятно, что замена логического «ИЛИ/И» на арифметические «минимум/плюс» превращает его результат в общий алгоритм кратчайших путей.
📌 Обнаружение отрицательных циклов через диагональ итоговой матрицы Флойда-Уоршелла — один из способов автоматического поиска арбитражных возможностей на валютных и товарных биржах: переход к весам $-\ln(\text{курс})$ превращает задачу «найти цикл обмена с прибылью» в задачу «найти отрицательный цикл», для которой готовое решение уже есть.
Лайфхаки и полезные трюки
💡 Прежде чем выбирать между Флойдом-Уоршеллом и многократным запуском Дейкстры, задай себе два вопроса: «Сколько вершин в графе?» и «Граф плотный или разреженный?» — для небольших плотных графов или при наличии отрицательных весов Флойд-Уоршелл почти всегда выигрывает по простоте и часто по скорости, для крупных разреженных графов почти всегда выгоднее многократная Дейкстра или алгоритм Джонсона.
💡 Если тебе нужно только проверить наличие отрицательного цикла в графе, а не вычислять полную матрицу расстояний, часто эффективнее алгоритм Беллмана-Форда из одной фиктивной вершины, соединённой рёбрами нулевого веса со всеми остальными, — Флойд-Уоршелл для этой узкой задачи избыточен по вычислениям, хотя и тоже корректен.
💡 При работе с реальными данными всегда используй настоящую бесконечность с плавающей точкой (float('inf') в Python) для кодирования недостижимости, а не произвольно большое целое число — это избавляет от риска переполнения при суммировании двух «псевдобесконечностей» на разреженных участках графа.
💡 Если тебе нужен не только ответ «на сколько», но и «через какие вершины», заведи матрицу next[i][j] с самого начала — добавлять её постфактум, когда уже потерян порядок вычислений, значительно сложнее, чем поддерживать параллельно с самого первого прохода алгоритма.
💡 Прежде чем доверять любым посчитанным «расстояниям» в графе, где веса рёбер теоретически могли быть отрицательными (курсы обмена, бонусные баллы, штрафы и надбавки), в первую очередь проверь диагональ итоговой матрицы — привычка на автомате запускать эту проверку экономит часы отладки, когда однажды в данных действительно окажется отрицательный цикл.
💡 Если граф часто, но понемногу меняется (добавилось или изменилось одно ребро), не пересчитывай всю матрицу $O(V^3)$ с нуля — для единственного изменённого ребра можно выполнить частичное обновление, рассматривая только его как единственную «новую» промежуточную возможность, что кардинально быстрее полного повторного прогона.
Три вложенных цикла, одна простая формула — и всё же за этим алгоритмом стоит одна из самых переиспользуемых идей в информатике: разбить сложную задачу на последовательность подзадач с постепенно расширяющимися возможностями и позволить каждой следующей подзадаче опираться на уже готовый, финализированный результат предыдущей. Ты увидел, как эта идея решает конкретную, практичную задачу поиска кратчайших маршрутов между городами или серверами, как она справляется с отрицательными весами там, где жадные алгоритмы вроде Дейкстры пасуют, и как честно признаёт свой предел — отрицательный цикл — вместо того чтобы молча выдавать бессмысленный ответ. Но ещё важнее увидеть в этой формуле не конкретный рецепт для конкретного графа, а общий паттерн: та же логика «минимум по альтернативным переходам через уже решённые подзадачи» встретится тебе снова — в выравнивании последовательностей ДНК, в проверке орфографии, в разборе языковых моделей и далеко за пределами теории графов. В следующем уроке ты увидишь ещё одну классическую задачу на взвешенных графах — минимальное остовное дерево, — которая, несмотря на внешнее сходство постановки, решается совершенно другим семейством идей, и это сравнение поможет тебе ещё точнее понимать, какой инструмент когда доставать из общего алгоритмического арсенала.
Понял тему? Закрепи в боте! 🚀
Попрактикуйся на задачах и получи персональные рекомендации от AI
💪 Начать тренировку