Алгоритм Флойда-Уоршелла: кратчайшие пути между всеми парами

Коротко

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

Какую задачу решает

Дейкстра находит кратчайшие пути от одной вершины ко всем остальным. Флойд-Уоршелл находит их между всеми парами сразу.

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

Если вершин немного (до нескольких сотен), а нужны все пары — это лучший выбор. Код помещается в десять строк.

Идея: разрешаем промежуточные вершины по одной

Здесь важно правильно понять логику, иначе алгоритм выглядит как магия.

Обозначим dist[i][j] — длину кратчайшего пути из i в j. Изначально это просто вес прямого ребра (или бесконечность, если ребра нет).

Теперь спросим: а что, если разрешить проходить через вершину 0? Тогда для каждой пары (i, j) проверим, не короче ли путь i → 0 → j, чем прямой.

Потом разрешим проходить через вершину 0 и 1. Потом через 0, 1, 2. И так далее.

После того как мы перебрали все вершины в качестве промежуточных, dist[i][j] содержит настоящий кратчайший путь — потому что любой путь состоит из каких-то промежуточных вершин, и все варианты уже рассмотрены.

Ключевая строка алгоритма:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Читается так: «путь из i в j — это либо то, что уже было, либо путь через k, если он короче».

Порядок циклов решает всё

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

INF = float('inf')


def floyd_warshall(graph: list[list[float]]) -> list[list[float]]:
    n = len(graph)
    dist = [row[:] for row in graph]  # копия, чтобы не портить вход

    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


# граф из 4 вершин, INF = ребра нет
graph = [
    [0,   5,   INF, 10],
    [INF, 0,   3,   INF],
    [INF, INF, 0,   1],
    [INF, INF, INF, 0],
]

for row in floyd_warshall(graph):
    print(row)
# [0, 5, 8, 9]
# [inf, 0, 3, 4]
# [inf, inf, 0, 1]
# [inf, inf, inf, 0]

Путь из вершины 0 в вершину 3 сократился с 10 (прямое ребро) до 9 — через маршрут 0 → 1 → 2 → 3.

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

Восстановление самого пути

Матрица расстояний говорит, насколько далеко, но не говорит, как идти. Чтобы восстановить маршрут, заведём вторую матрицу — «следующая вершина на пути».

def floyd_with_path(graph: list[list[float]]):
    n = len(graph)
    dist = [row[:] for row in graph]
    # next_v[i][j] — куда шагнуть из i, чтобы попасть в j
    next_v = [[j if graph[i][j] != INF else None for j in range(n)]
              for i in range(n)]

    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]
                    next_v[i][j] = next_v[i][k]  # первый шаг — как до k

    return dist, next_v


def restore_path(next_v, u: int, v: int) -> list[int]:
    if next_v[u][v] is None:
        return []          # пути нет

    path = [u]
    while u != v:
        u = next_v[u][v]
        path.append(u)
    return path


dist, next_v = floyd_with_path(graph)
print(restore_path(next_v, 0, 3))  # [0, 1, 2, 3]

Отрицательные веса и отрицательные циклы

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

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

def has_negative_cycle(dist: list[list[float]]) -> bool:
    # путь из вершины в саму себя стал отрицательным — есть цикл
    return any(dist[i][i] < 0 for i in range(len(dist)))

Если dist[i][i] < 0, значит нашёлся путь из вершины в саму себя с отрицательной суммой весов — это и есть отрицательный цикл.

Сравнение с другими алгоритмами

Когда что выбирать:

• Нужны все пары, вершин мало (V ≤ 400) — Флойд-Уоршелл. Простой код, предсказуемое время.
• Нужны все пары, граф разреженный и большой — V запусков Дейкстры окажется быстрее: O(V·E log V) против O(V³).
• Нужен путь от одной вершины — Дейкстра, а при отрицательных весах Беллман-Форд.

Неочевидные применения

Алгоритм решает не только задачу о расстояниях. Та же схема из трёх циклов работает, если заменить операции.

Транзитивное замыкание — достижима ли вершина j из i. Заменяем min на or, а сложение на and:

reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

Это называется алгоритмом Уоршелла.

Максимальная пропускная способность пути — вместо суммы берём минимум по рёбрам, вместо минимума максимум:

cap[i][j] = max(cap[i][j], min(cap[i][k], cap[k][j]))

Диаметр графа — максимум по всей матрице расстояний после работы алгоритма.

Частые ошибки

Неправильный порядок циклов. Разбирали выше — k обязательно снаружи. Это ошибка номер один.

Ненулевая диагональ на старте. dist[i][i] должно быть 0, иначе алгоритм решит, что путь из вершины в саму себя чего-то стоит.

Переполнение при сложении бесконечностей. В Python float('inf') складывается корректно. В языках, где бесконечность изображают большим целым (например, 1e9), сумма двух таких значений может переполниться или дать ложное «улучшение». Там нужна проверка if dist[i][k] != INF and dist[k][j] != INF.

Модификация входной матрицы. Копируйте её перед работой, если она нужна вызывающему коду.

Что запомнить

• Алгоритм находит кратчайшие пути между всеми парами вершин за O(V³).
• Идея: последовательно разрешаем использовать вершины 0, 1, 2, … как промежуточные.
• Промежуточная вершина k — обязательно во внешнем цикле.
• Работает с отрицательными весами и обнаруживает отрицательные циклы по диагонали.
• Та же схема решает транзитивное замыкание и задачи на максимум-минимум по пути.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→