Флойд-Уоршелл: три цикла, которые считают всё

Коротко

Если нужны расстояния между ВСЕМИ парами вершин, можно V раз запустить Дейкстру - а можно взять алгоритм из трёх вложенных циклов, который умещается в пять строк. Флойд-Уоршелл строит ответ по числу разрешённых ПРОМЕЖУТОЧНЫХ вершин: сперва пути, идущие напрямую, потом те, которым можно проходить через вершину 0, потом через 0 и 1, и так далее (вершины, как везде в курсе, нумеруются с нуля). Ключ - в порядке циклов: k (через что разрешено идти) обязан быть САМЫМ ВНЕШНИМ, иначе алгоритм считает не то. Цена O(V³) времени и O(V²) памяти, веса любые, включая отрицательные; отрицательный цикл виден сразу - у какой-нибудь вершины расстояние до себя становится отрицательным.

Если ты знаешь формулу через промежуточную вершину, помнишь, почему k идёт снаружи, и умеешь ловить отрицательный цикл по диагонали, листай до «Теперь сам».

Как думаешь, что взять за «подзадачу»

Дейкстра строила ответ, наращивая множество обработанных вершин. Прежде чем читать дальше, подумай: если считать расстояния СРАЗУ между всеми парами, по какому параметру их наращивать? Подсказка: путь из i в j описывается не только концами, но и тем, через какие вершины ему разрешено проходить.

На что это похоже

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

Механизм: три цикла и смысл каждого

# d[i][j] - вес ребра i→j, INF если ребра нет, d[i][i] = 0
for k in range(V):                 # РАЗРЕШАЕМ проходить через вершину k
    for i in range(V):
        for j in range(V):
            if d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]

Смысл величины после k-го шага: d[i][j] - длина кратчайшего пути из i в j, которому разрешено проходить только через вершины с номерами меньше или равными k. Формула разбирает два случая: путь либо не заходит в k вовсе (тогда старое значение), либо заходит ровно один раз (тогда он распадается на i → k и k → j, и оба куска уже посчитаны).

почему «ровно один раз»: если путь заходит в k дважды, между заходами получается цикл;
при отсутствии отрицательных циклов его можно выбросить, не удлинив путь

Восстановление самих маршрутов - через матрицу «следующая вершина»:

# рядом с инициализацией d: если ребро i → j есть, первый шаг маршрута - сразу j
nxt = [[j if d[i][j] < INF else -1 for j in range(V)] for i in range(V)]

# ВНУТРИ тройного цикла, вместо строки с min:
if d[i][k] + d[k][j] < d[i][j]:
    d[i][j] = d[i][k] + d[k][j]
    nxt[i][j] = nxt[i][k]          # первый шаг маршрута теперь ведёт в сторону k

# после работы алгоритма маршрут читается так:
def path(i, j):
    if nxt[i][j] == -1:
        return []                  # пути нет
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route

Отрицательный цикл обнаруживается бесплатно: если после работы алгоритма d[i][i] < 0 хотя бы для одной вершины, значит из i можно вернуться в i, потратив отрицательную величину.

Правило

Флойд-Уоршелл: три вложенных цикла, k снаружи, d[i][j] = min(d[i][j], d[i][k] + d[k][j]). После k-й итерации d[i][j] - кратчайший путь, которому разрешены промежуточные вершины с номерами <= k. Цена O(V³) времени, O(V²) памяти; веса любые, кроме отрицательных циклов - они обнаруживаются условием d[i][i] < 0. Порядок циклов обязателен: k внешний, i и j внутри в любом порядке. Маршруты восстанавливаются матрицей nxt.

Разбор: почему k обязан быть снаружи

Это главная ловушка алгоритма, и она стоит отдельного разбора.

Внешний цикл по k означает: «на этом шаге мы разрешаем всем парам пользоваться вершиной k». К моменту, когда мы считаем d[i][k] + d[k][j], оба слагаемых уже учитывают все вершины < k - именно это делает формулу корректной.

Если вынести наружу i (то есть перебирать сначала все k для первой строки, потом для второй), рассуждение рушится: считая d[i][k], мы обратимся к значениям, для которых ещё не перебраны все промежуточные вершины. Алгоритм что-то посчитает, местами даже правильно - но гарантии не будет, и на подходящем графе ответ окажется завышенным.

Полезная проверка на понимание: поменять местами i и j во внутренних циклах МОЖНО - от этого ничего не зависит, потому что при фиксированном k все пары независимы друг от друга. А вот тронуть k нельзя.

Разбор: считаем матрицу по шагам

Граф из трёх вершин: 0→1 = 4, 1→2 = 1, 0→2 = 9, 2→0 = 2.

начальная матрица d (строка - откуда, столбец - куда, ∞ - нет ребра):

      0    1    2
  0 [ 0    4    9 ]
  1 [ ∞    0    1 ]
  2 [ 2    ∞    0 ]

k = 0 (разрешили проходить через вершину 0):
    d[1][2]? через 0: d[1][0] + d[0][2] = ∞ - нет
    d[2][1]? через 0: d[2][0] + d[0][1] = 2 + 4 = 6 < ∞  → d[2][1] = 6
    (остальные семь пар алгоритм тоже перебирает - я выписываю только те,
     где сумма вообще конечна: в прочих один из двух кусков равен ∞)
k = 1 (теперь можно через 0 и 1):
    d[0][2]? через 1: d[0][1] + d[1][2] = 4 + 1 = 5 < 9  → d[0][2] = 5
    d[2][2]? через 1: d[2][1] + d[1][2] = 6 + 1 = 7, но d[2][2] = 0 - не лучше
k = 2 (можно через любые):
    d[1][0]? через 2: d[1][2] + d[2][0] = 1 + 2 = 3 < ∞  → d[1][0] = 3
    d[1][1]? через 2: d[1][2] + d[2][1] = 1 + 6 = 7, d[1][1] = 0 - не лучше
    d[0][1]? через 2: d[0][2] + d[2][1] = 5 + 6 = 11, хуже 4

итог:
      0    1    2
  0 [ 0    4    5 ]
  1 [ 3    0    1 ]
  2 [ 2    6    0 ]

Проверим одно значение руками: d[2][1] = 6 - это маршрут 2 → 0 → 1 длиной 2 + 4. Прямого ребра из 2 в 1 нет, и другого пути тоже. Сходится. И заметь, что диагональ осталась нулевой: отрицательных циклов в графе нет.

Что ломается без этого

Первое, самое частое: перепутать порядок циклов и поставить k не снаружи - ответ станет неверным молча, причём на многих графах совпадёт с правильным. Второе: забыть инициализацию d[i][i] = 0 - диагональ останется бесконечной, и пути «через себя» начнут ломать формулу. Третье: считать INF + INF без защиты. В Python целые не переполняются, поэтому там беда мягче: получится «почти бесконечность», которая вдруг окажется меньше INF, и в матрице появится несуществующий путь. В языках с фиксированными целыми (C, Java, Go) то же сложение даст настоящее переполнение и отрицательное число, а это уже «путь длиной минус два миллиарда»; обычно берут INF заведомо меньше половины максимального числа. Четвёртое: применять алгоритм к графу с отрицательным циклом и ожидать осмысленных расстояний - надо сначала проверить диагональ. Пятое: запускать O(V³) на графе с десятью тысячами вершин: это 10¹² операций, то есть часы; для больших разреженных графов нужен другой подход - следующий урок.

Зачем это в работе

Флойд-Уоршелл берут там, где вершин немного (сотни), а пар нужно много: матрицы расстояний между городами или складами, метрики «все ко всем» в небольших сетях, предподсчёт для быстрых ответов на множество запросов. Но главная ценность - шаблон. Та же тройка циклов решает целый класс задач, если поменять операции: заменив min на «логическое ИЛИ», а сложение на «И», получаем ТРАНЗИТИВНОЕ ЗАМЫКАНИЕ (кто до кого вообще достижим) - это алгоритм Уоршелла; заменив min на max, а сложение на min, получаем «путь с максимальной пропускной способностью» - задачу про самое узкое место маршрута. Такие обобщения называют алгеброй путей: меняются операции, а структура алгоритма остаётся. Об этом подробнее в третьем уроке главы.

Теперь сам

Граф: 0→1 = 3, 1→2 = 2, 2→0 = −4, 0→2 = 8. Посчитай матрицу Флойда-Уоршелла и скажи, что в ней покажет отрицательный цикл.

Ответ. Начальная матрица (диагональ нулевая, отсутствующие рёбра - ∞): d[0][1] = 3, d[0][2] = 8, d[1][2] = 2, d[2][0] = −4, остальные внедиагональные ∞.

k = 0: d[2][1] через ноль: d[2][0] + d[0][1] = −4 + 3 = −1 < ∞ → d[2][1] = −1. k = 1: d[0][2] через единицу: 3 + 2 = 5 < 8 → d[0][2] = 5; d[2][2] через единицу: d[2][1] + d[1][2] = −1 + 2 = 1, это больше нуля - не лучше. k = 2: d[1][0] через двойку: d[1][2] + d[2][0] = 2 + (−4) = −2 < ∞ → d[1][0] = −2; d[0][0] через двойку: d[0][2] + d[2][0] = 5 + (−4) = 1 > 0 - не лучше; d[1][1] через двойку: d[1][2] + d[2][1] = 2 + (−1) = 1 > 0 - не лучше; d[2][2]: d[2][0] + d[0][2] = −4 + 5 = 1 > 0.

Диагональ осталась нулевой, значит отрицательного цикла нет. Проверим прямо: цикл 0→1→2→0 весит 3 + 2 − 4 = 1 > 0, цикл 0→2→0 весит 8 − 4 = 4 > 0. Верно.

А теперь измени вес 2→0 на −6. Тогда цикл 0→1→2→0 станет весить 3 + 2 − 6 = −1, и на шаге k = 2 получится d[0][0] = d[0][2] + d[2][0] = 5 + (−6) = −1 < 0 - отрицательное число на диагонали. Это и есть признак: из вершины 0 можно вернуться в неё саму, потратив −1, а значит кратчайших путей в графе не существует.

Главное

Флойд-Уоршелл считает расстояния между всеми парами тремя вложенными циклами, наращивая множество РАЗРЕШЁННЫХ промежуточных вершин: после k-й итерации d[i][j] - кратчайший путь, которому можно проходить только через вершины с номерами <= k. Формула разбирает два случая - путь либо не заходит в k, либо заходит ровно один раз и распадается на две уже посчитанные половины (дважды заходить незачем: между заходами был бы цикл, а его при отсутствии отрицательных циклов можно выбросить). Порядок циклов обязателен: k СНАРУЖИ; переставить i и j между собой можно, k тронуть нельзя - иначе слагаемые окажутся недосчитанными и ответ завысится, причём молча. Цена O(V³) времени и O(V²) памяти, веса любые; отрицательный цикл виден как d[i][i] < 0. Маршруты восстанавливают матрицей nxt. Алгоритм хорош при небольшом V и нужде во всех парах; на больших разреженных графах он не годится - там Джонсон. И отдельно стоит запомнить его как ШАБЛОН: замена операций даёт транзитивное замыкание и задачу о самом узком месте маршрута.