Разбираем алгоритм Флойда-Уоршелла: от теории к задачам ЕГЭ

** изображение создано или обработано с помощью ИИ.

Что такое алгоритм Флойда и зачем он нужен в ЕГЭ?

В задачах ЕГЭ по информатике часто требуется найти путь в графе — например, в дорожной сети между городами или в таблице авиарейсов. Но нередко нужна не просто длина маршрута из А в Б, а полная картина: как добраться от каждой вершины до каждой. Здесь применяется алгоритм Флойда-Уоршелла.

Место алгоритма в теории графов и кодификаторе ЕГЭ

Этот метод — классика динамического программирования. Суть подхода проста: сложная задача разбивается на мелкие шаги, и уже найденные решения переиспользуются. В кодификаторе ЕГЭ тема напрямую связана с разделами Теория графов и Динамическое программирование.

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

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

Ключевая идея: матрица кратчайших расстояний

Матрица — это квадратная таблица, где строки и столбцы — вершины графа. На пересечении строки i и столбца j стоит число d_ij — текущее известное расстояние из пункта i в пункт j. Алгоритм заполняет эту таблицу так, чтобы каждое значение стало минимально возможным.

Логика уточнения значений проста. Задаётся вопрос: а не будет ли путь из i в j короче, если зайти по дороге в точку k? Перебираются все возможные промежуточные вершины, и ячейки матрицы постоянно обновляются по правилу:

d_ij = min(d_ij, d_ik + d_kj)

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

Когда выбирают этот алгоритм, а не Дейкстру?

Возникает вопрос: зачем использовать Флойда, если есть Дейкстра? Выбор зависит от задачи. Флойд работает за O(n в кубе), и если нужен путь от одной конкретной станции до всех других, Дейкстра окажется быстрее.

Однако в задачах ЕГЭ на графы фокус часто смещается. Количество вершин в экзаменационных задачах редко превышает 50–100 предметов, а для таких масштабов тройной цикл в Python отрабатывает мгновенно. Представим плотный граф, где почти каждая вершина соединена с соседней. Здесь Флойд не только проще в реализации (всего четыре строки кода с тремя вложенными циклами for), но и не требует громоздких структур данных вроде очередей с приоритетами, которые легко перепутать на экзамене под воздействием стресса.

Более того, если по условию нужно понять, можно ли вообще из точки А попасть в точку Б (задача о связности) или найти длину самого выгодного маршрута среди всех возможных пар, перед нами прямое показание к применению метода Флойда-Уоршелла.

Как работает алгоритм Флойда: пошаговый разбор с матрицами

** изображение создано или обработано с помощью ИИ.

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

Его главное оружие — релаксация рёбер графа. Это простое правило: если путь от i к j через точку пересадки k оказывается короче старого маршрута, расстояние обновляется. Вся логика заключена в одной формуле: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

Далее пошагово разбирается, как это оживает в таблицах.

Шаг 0: Как составить матрицу весов по графу

Первый этап на экзамене — перевести рисунок или список рёбер в матрицу смежности. Граф можно представить как таблицу: строки — это точки старта, столбцы — точки назначения. Если из A в B ведёт дорога длиной 5, ставится число 5 на пересечении строки A и столбца B. Когда граф неориентированный и движение разрешено в обе стороны, матрица становится симметричной.

Что делать с пустыми клетками, где связи нет? Главная ошибка новичков — ставить ноль. Ноль означает, что путь мгновенный, то есть бесплатный. Если проезда нет, ставится бесконечность. В коде на Python для ЕГЭ в качестве бесконечности используют float(‘inf’) или условное огромное число, например, 10 в 9 степени, которое заведомо длиннее любого возможного маршрута.

На главной диагонали (A–A, B–B) всегда остаются нули: стоять на месте можно без затрат. Так создается стартовая площадка для вложенных циклов в коде.

Итерация k=1: пробуем пройти через первую вершину

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

Внутренние циклы перебирают все пары (i, j). Например, прямой путь из города 2 в город 3 изначально равен 8. Алгоритм смотрит: путь из 2 в 1 равен 3, а из 1 в 3 равен 4. Сумма через пересадку в городе 1 составляет: 3 + 4 = 7. Сравниваем старое значение и новое: 8 или 7? Побеждает 7. Ячейка матрицы на пересечении 2 строки и 3 столбца перезаписывается числом 7.

Если бы сумма через промежуточную вершину оказалась больше или связи через k не существовало (там стояла бесконечность), значение ячейки осталось бы прежним.

Завершение работы и анализ результата

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

После n итераций получается финальная матрица кратчайших расстояний. Её преимущество в том, что она дает прямой ответ на любой вопрос: чтобы узнать длину кратчайшего пути из города X в город Y, достаточно посмотреть на пересечение строки X и столбца Y.

Особый случай — поиск циклов отрицательного веса. В реальном мире невозможно потратить бензин со знаком минус, но в компьютерных моделях или задачах на оптимизацию расходов такое случается. Когда все итерации алгоритма завершены, проверяется главная диагональ матрицы. Если там появился минус (хотя бы один элемент d[i][i] стал меньше нуля), граф содержит отрицательный цикл. Это значит, что можно уйти из вершины, покружить по циклу и вернуться обратно, бесконечно уменьшая итоговую стоимость пути.

Для задач ЕГЭ появление минуса на диагонали — это маркер того, что в графе нет конечного кратчайшего пути, так как его можно уменьшать до бесконечности.

Разбор типовых задач ЕГЭ с алгоритмом Флойда

** изображение создано или обработано с помощью ИИ.

В задачах ЕГЭ алгоритм Флойда проверяет понимание принципов динамического программирования. Не придется писать огромные программы — чаще всего на экзамене достаточно вручную обновить матрицу расстояний или восстановить логику программного шага. Ниже представлены три классических сценария.

Задача 1: Восстановление матрицы на k-м шаге

В задании приведена начальная матрица весов W для графа из четырёх вершин. Известно, что алгоритм Флойда выполнил первую итерацию при k = 1 (вершина 1 использовалась как промежуточная). Требуется определить, как изменится матрица.

Начальная матрица W имеет вид (символ бесконечности означает отсутствие прямого ребра):

1. Строка 1: 0, 5, 9, ∞
2. Строка 2: ∞, 0, 2, 8
3. Строка 3: ∞, ∞, 0, 3
4. Строка 4: 4, ∞, ∞, 0

Выполним шаг k = 1 вручную. Необходимо проверить все пары вершин i и j по формуле:
W[i][j] = min(W[i][j], W[i][k] + W[k][j]).

Найдём элемент, который гарантированно изменится. Рассмотрим вершину 4: из неё есть путь в вершину 1 (W = 4), а из вершины 1 есть путь в вершину 2 (W = 5). Проверим элемент W[4][2], изначально равный бесконечности:
W[4][2] = min(∞, W[4][1] + W[1][2]) = min(∞, 4 + 5) = 9.

Таким образом, после первой итерации элемент на пересечении 4-й строки и 2-го столбца обновится с ∞ на 9. Остальные элементы, до которых нельзя добраться через вершину 1, останутся прежними.

Задача 2: Нахождение длины кратчайшего пути для конкретной пары вершин

Требуется найти кратчайшее расстояние от вершины A до вершины E в ориентированном графе. Рёбра заданы списком: A-B (2), A-C (4), B-C (1), B-D (7), C-E (3), D-E (1), E-A (6). Остальные связи отсутствуют. Логика работы алгоритма Флойда по шагам:

1. На итерации k = A проверяются пути через вершину A. Поскольку это стартовая точка для многих маршрутов, прямые пути из неё не улучшаются.
2. На итерации k = B алгоритм проверяет, можно ли улучшить путь из A в C через B. Прямой путь A-C равен 4. Путь через B: A-B + B-C = 2 + 1 = 3. Поскольку 3 меньше 4, кратчайший путь из A в C становится равен 3.
3. На итерации k = C алгоритм проверяет путь из A в E через вершину C. Уже известно, что лучший путь до C равен 3. Путь C-E равен 3. Итого путь A-B-C-E равен 3 + 3 = 6.
4. На итерации k = D проверяется путь через D. Маршрут A-B-D-E равен 2 + 7 + 1 = 10. Это хуже уже найденного варианта 6.

Итоговый ответ для кратчайшего пути из A в E равен 6. При ручном просчёте на ЕГЭ всегда следует обращать внимание на направленность стрелок: если ребро идёт только из E в A, использовать его для пути из A в E нельзя.

Задача 3: Программная реализация на Python для ЕГЭ

В некоторых комплексных задачах компьютерного эксперимента на ЕГЭ проще запустить готовый скрипт. Вот лаконичный и надежный шаблон алгоритма Флойда-Уоршелла на Python:

# Предположим, данные считываются из файла, где n — количество вершин

with open(«17.txt») as f:

n = int(f.readline())

INF = 10 ** 9

# Изначально заполняем матрицу бесконечностями

W = [[INF] * n for _ in range(n)]

# Главную диагональ заполняем нулями

for i in range(n):

W[i][i] = 0

# Считываем ребра графа из файла

for line in f:

if line.strip():

u, v, weight = map(int, line.split())

W[u][v] = weight # Для ориентированного графа

# W[v][u] = weight # Раскомментировать, если граф неориентированный

# Три вложенных цикла алгоритма Флойда

for k in range(n):

for i in range(n):

for j in range(n):

if W[i][k] + W[k][j] < W[i][j]:

W[i][j] = W[i][k] + W[k][j]

# Вывод кратчайшего расстояния от вершины 0 до вершины n-1

print(W[0][n-1])

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

Анализ эффективности и ограничения алгоритма

Алгоритм Флойда-Уоршелла изящно решает задачу поиска кратчайших путей между всеми парами вершин. Но за изящество приходится платить. Разберём, где алгоритм хорош, а где требует осторожности.

Сложность по времени и памяти

Три вложенных цикла, каждый из которых пробегает по всем n вершинам, дают алгоритмическую сложность O(n в кубе). На практике это означает: если вершин станет в 10 раз больше, вычисления займут в 1000 раз больше времени.

Для сравнения, алгоритм Дейкстры ищет путь от одной вершины до всех остальных за O(m log n), где m — количество рёбер. Если нужны пути от каждой вершины до каждой, можно запустить Дейкстру n раз. Тогда сложность составит O(n m log n). В разреженных графах (где мало рёбер) такой подход обгонит кубическую сложность Флойда. Но стоит графу стать плотным, как алгоритм Флойда с его простотой и предсказуемостью часто берёт реванш.

В задачах ЕГЭ граф редко содержит больше 10–15 городов или пунктов. Здесь кубическая сложность — вовсе не препятствие. Компьютер выполнит 15 в кубе = 3375 операций почти мгновенно. На первый план выходит простота реализации: за несколько минут пишется тройной цикл, и получаются ответы на все вопросы задачи без риска запутаться в очередях с приоритетом.

Проблема отрицательных циклов

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

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

Как это проявляется в матрице? Очень просто. Путь из вершины в неё же всегда начинается с нуля. Если после работы алгоритма на главной диагонали появилось отрицательное число (W[i][i] < 0), значит, вершина i входит в отрицательный цикл. Это верный признак некорректной постановки задачи поиска кратчайшего пути. Остальным значениям в таблице верить уже нельзя.

Где еще применяется алгоритм Флойда-Уоршелла

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

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

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

В онлайн-школе ЕГЭLAND преподаватели информатики помогают освоить этот алгоритм: разбирают типовые задачи, учат работать с матрицами и отрабатывают программную реализацию на Python. Записаться на пробное занятие можно на сайте школы.