Зачем нужен алгоритм Флойда на экзамене
Задачи на кратчайшие пути встречаются почти в каждом варианте. Чаще всего это задачи 27 или 30. Алгоритм Флойда подходит, когда нужно найти длины всех пар вершин. Он решает проблему за кубическое время и легко кодируется. Экзамен ценит простые и универсальные идеи. Поэтому школьнику выгодно выучить именно этот метод. Если граф содержит до сорока вершин, время работы уложится в лимит Python. А таких размерностей на ЕГЭ достаточно.
Ключевая идея: динамическое обновление расстояний
Метод строится на принципе релаксации через промежуточные вершины. Сначала расстояния известны только для прямых ребер. Затем перебираем каждую вершину k. Для каждой пары i, j проверяем, выгодно ли идти через k. Формула выглядит так: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). После n итераций матрица d хранит длины всех кратчайших путей. Красивая особенность: код занимает пять-шесть строк. Это снижает шанс допустить ошибку на стрессовом экзамене.
Формат задач в КИМ ЕГЭ
Существует три популярных формата.
- Найти одну минимальную длину между заданными вершинами.
- Определить, какие ребра можно удалить без увеличения самого длинного пути.
- Подсчитать количество пар с расстоянием меньше заданного порога.
Во всех случаях нужна таблица расстояний. Поэтому Флойд кажется естественным. Иногда авторы дают взвешенный ориентированный граф. Иногда граф неориентированный. В последнем случае матрица симметрична. Это даёт шанс ускорить вычисления, перебирая лишь половину ячеек. Но на экзамене легче писать полный цикл и не тратить время на оптимизацию.
Пошаговый разбор мини-примера
Возьмём учебный граф из пяти вершин. Рёбра такие: 1-2 (3), 1-3 (8), 2-3 (2), 2-4 (5), 3-4 (1), 4-5 (4). В скобках длины. Нужно получить длину кратчайшего пути от 1 до 5.
Шаг 1. Создаём матрицу 5×5. На диагонали нули. Там, где ребро есть, ставим вес. Остальное заполняем большим числом, например 10**9.
Шаг 2. Перебираем k=1. Для каждой пары i, j проверяем обход через 1. После этого шага изменятся только пути, проходящие через вершину 1. Например, d[2][3] уже равен 2, лучше не станет.
Шаг 3. k=2. Теперь d[1][3] уменьшится с 8 до 5, потому что 1-2-3 весит 3+2. Другие пары тоже могут сократиться.
Шаг 4. k=3. Путь 1-3-4 даёт длину 6, что лучше прежних 9. Обновляем d[1][4] и d[4][1].
Шаг 5. k=4. Появляется вариант 1-4-5 длиной 10. Запоминаем.
Шаг 6. k=5 ничего не меняет, потому что 5 имеет только одно ребро.
Ответ d[1][5] равен 10. Алгоритм выполнил 125 проверок, что мало даже для калькулятора.
Типичные ловушки и ошибки
- Забывают копировать матрицу для разных тестов. Старые значения портят новые.
- Сравнивают с INF, но выбирают слишком маленькое INF. Тогда сложение переполняется.
- Начинают цикл не с k, а сразу с i и j. Порядок важен!
- Пытаются хранить матрицу как список строк. Из-за ссылки меняются все строки сразу. Используйте генератор списков.
- Ставят INF = 10**9, но в задаче вес ребра может быть 10**9. Лучше взять 10**12.
- Пишут вложенные циклы без ускорения ввода. На больших графах надо использовать sys.stdin.buffer.
Оптимизация кода на Python
Сама идея проста, но реализация может тормозить. Несколько советов помогут уложиться в лимит.
- Используйте локальные переменные внутри тройного цикла. Это снижает время доступа.
- Отключите проверку if d_ik + d_kj < d_ij в отдельной функции. Внутри цикла она будет медленнее.
- Часто n ≤ 50. Тогда trilinear цикл выполняется 125 000 итераций, что быстро.
- Подготовьте шаблон заранее. На экзамене вас спасут готовые шесть строк.
- Если нужен путь, а не только длина, храните ещё матрицу предков. Она восстанавливает путь за O(n).
Ниже приведён минимальный рабочий пример:
from sys import stdin
n = int(stdin.readline())
INF = 10**12
d = [[INF]*n for _ in range(n)]
for i in range(n):
row = list(map(int, stdin.readline().split()))
for j, w in enumerate(row):
if w != -1: d[i][j] = w
for k in range(n):
for i in range(n):
dik = d[i][k]
for j in range(n):
new = dik + d[k][j]
if new < d[i][j]: d[i][j] = new
Тренировочные задания для самостоятельной практики
- Открытый банк ФИПИ. Скачайте задания 27 за последние пять лет.
- Сайт acmp.ru. Задача 27 «Поездка в Европу» отлично подходит.
- Учебник Савина, глава «Алгоритмы на графах», задача 3.16.
- Создайте случайный неориентированный граф с пятью вершинами. На бумаге пройдите Флойда вручную.
- После кода проверьте себя, сравнив результат с библиотекой networkx.
Практика закрепит навык и уменьшит стресс. В день экзамена вам нужно писать код почти автоматически.
Чек-лист перед экзаменом
- Запомните шесть строк кода Флойда.
- Подготовьте шаблон чтения матрицы и вывод нужного ответа.
- Выберите безопасное значение INF > n * max_weight.
- Проверьте, что понимаете разницу между ориентированным и неориентированным графом.
- Научитесь восстанавливать путь при необходимости.
- Сделайте пять полных пробных работ с таймером.
- Запланируйте повторение теории за день до ЕГЭ.
- Рассмотрите вариант онлайн курс подготовки к ЕГЭ, если чувствуете, что нужна поддержка.
Следуя чек-листу, вы снизите риск глупых ошибок. А значит получите заветные баллы и поступите в желанный вуз.