Что решает алгоритм Флойда
На ЕГЭ по информатике часто дают задачи на кратчайшие пути, и алгоритм Флойда сразу приходит на ум. Этот метод ищет расстояния между каждой парой вершин во взвешенном графе с положительными и отрицательными, но безотрицательных циклов. Формулировка выглядит громоздкой, однако сама процедура компактна и строго детерминирована. Учащемуся важно понять, зачем она нужна: иногда задача требует не одного, а сотен ответов о разных парах городов, станций или серверов. Перезапускать Дейкстру для каждой пары медленно, а Флойд решает всё за один проход. Таким образом время окупается, хотя число вершин не должно быть слишком большим.
Базовая идея: динамическое программирование на графах
Решение строится по принципу «разбиваем путь на части». Пусть k — номер промежуточной вершины, которую уже разрешено использовать. Тогда di,jk — минимальная длина пути от i к j, позволяющего проходить лишь через вершины 1…k. Рекуррентная формула короткая: di,jk = min(di,jk-1, di,kk-1 + dk,jk-1). Сначала учитываем ноль промежуточных вершин и берём исходные рёбра. На каждом шаге алгоритм пытается улучшить путь за счёт новой вершины. Фактически мы применяем динамическое программирование с тремя измерениями, но одно измерение к концу итерации можно перезаписать. Этим объясняется компактность памяти — в таблице остаётся лишь di,j, без индекса k.
В экзаменационной задаче формулу часто не требуют выводить, но спросить могут логику перехода. Держите идею «добавили ещё одну вершину, стало лучше или осталось старым» — так легче объяснить ход решения.
Таблица расстояний: как подготовить данные
Перед запуском алгоритма строится квадратная матрица n×n. На главную диагональ ставим нули. Если ребра между i и j нет, вводим «бесконечность» — обычно используют 109 или даже 1018 для long long. Ошибка здесь приводит к переполнению, поэтому выбирайте число вдвое меньше максимального типа. Граф неориентированный? Тогда di,j = dj,i. Ориентированный? Заполняем только заданные направления. В некоторых задачах нужно строить матрицу по списку город-дорога-длина, а иногда раздают готовую. Прочитайте условия: на ЕГЭ встречаются обе ситуации.
Для языков Python и Java матрицу удобнее хранить в списке списков. В C++ часто берут вектор векторов или статический массив, если n ≤ 100. Размер больше может не пройти по памяти, поэтому проверьте ограничения.
Три вложенных цикла без паники
Код пишут всего в пять строк:
- for k in range(n):
- for i in range(n):
- for j in range(n):
- d[i][j] = min(d[i][j], d[i][k] + d[k][j])
Важно правильно ставить индексы. Новички часто путают порядок циклов, но алгоритм симметричен, поэтому перестановка не ломает ответ, только немного влияет на кэш. Следите, чтобы переменная k была внешней: именно она расширяет множество промежуточных вершин. Проверку overflow помещайте до обновления: если d[i][k] или d[k][j] бесконечность, пропускайте сложение. В C++ это одно условие, в Python достаточно большого числа, перелива всё равно нет.
Оптимизации и типичные ловушки на ЕГЭ
Время работы O(n³). При n = 500 получается 125 миллионов операций, что в Питоне уже критично. Есть несколько выходов:
- Использовать PyPy, он выполняет тот же код быстрее.
- Переписать на C++ или Java, если экзамен позволяет выбор языка.
- Уменьшить внутренний цикл: пробрасывать только если d[i][k] + d[k][j] < d[i][j].
- Заранее отфильтровывать «тяжёлые» вершины, если по условию они никогда не участвуют.
Частые ошибки:
- Неинициализированные элементы матрицы.
- Отрицательный цикл: на ЕГЭ его обычно нет, но проверка лишней не будет.
- Перепутанные индексы при выводе ответа, особенно когда нумерация начинается с 1.
Разбор задачи из демо-версии
В демо-варианте 2024 года нужно найти минимальные расстояния между пунктами доставки. Вход: n ≤ 150 и m дорог. Требуется вывести сумму всех di,j для i < j. Решаем:
1. Читаем n и m, строим матрицу. 2. Запускаем наш тройной цикл. 3. Считаем нужную сумму. Код в C++ занимает 40 строк, а в Python чуть больше из-за чтения. Главное — не забыть, что сумма умещается в 64-битное целое, поэтому используем long long. После оптимизации проверки на бесконечность программа укладывается в 1 с на реальном железе.
Как проверить решение и оценить сложность
Тестируйте на маленьких графах, где ответ можно получить вручную. Например, треугольник с рёбрами 3, 4 и 5. Затем берите полный граф на 5 вершин со случайными весами. Итоговая таблица должна совпасть с результатами Дейкстры, запущенной для каждой вершины. Оценка памяти проста: n² ячеек по восемь байт — при n = 500 всего 2 МБ, свободно для любого языка. Время — куб, тут только замеры и оптимизация.
Следите за корректностью вывода. Формат «через пробел» и «каждая строка своя» иногда чередуются в разных заданиях.
Полезные ресурсы и следующий шаг
После понимания алгоритма потренируйтесь на площадках Acmp или Timus — там много задач на полный набор кратчайших путей. Читайте оригинальную работу Роберта Флойда, чтобы увидеть истоки метода. Для визуализации можно открыть интерактивные демонстрации в GraphOnline: там видно, как постепенно сужаются расстояния.
Нужна системная подготовка? Посмотрите курс «Информатика. ЕГЭ без паники» в онлайн школе el-ed.ru; там алгоритм Флойда объясняют, дают тесты и проверяют код. После отработки темы переходите к «Кёнигсу и дизъюнктам» — они тоже любят встречаться в части 2.