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

🎯 Зачем это нужно?

Представь, что ты планируешь маршруты доставки для крупной логистической компании 🚚. У тебя есть 1000 городов и нужно знать кратчайший путь между ЛЮБЫМИ двумя городами. Запускать алгоритм Дейкстры 1000 раз? Слишком медленно!

Или другой пример: в социальной сети нужно найти “степень разделения” между всеми пользователями - кто от кого на каком расстоянии. Facebook использует именно такие алгоритмы для рекомендации друзей!

🌍 Где применяется:

• Google Maps - предвычисление маршрутов между популярными точками
• Игровая индустрия - поиск путей для NPC в стратегиях
• Финансы - арбитраж валют (найти цепочку обменов для максимальной прибыли)

📚 История вопроса

Алгоритм назван в честь Роберта Флойда, но на самом деле его независимо открыли трое: Флойд (1962), Уоршелл (1962) и Рой (1959) 📅.

Интересный факт: Стивен Уоршелл изначально решал совсем другую задачу - находил транзитивное замыкание графа (какие вершины достижимы из каких). А уже потом поняли, что тот же принцип работает для кратчайших путей!

💡 Интуиция

Основная идея гениально проста: “А что если пойти через промежуточную вершину?” 🤔

Представь: ты едешь из города A в город C. Прямой путь занимает 100 км. Но есть город B - из A в B всего 30 км, а из B в C тоже 30 км. Итого 60 км через B - выгоднее!

[МЕДИА: image_01] Описание: Треугольник из трех городов A, B, C с расстояниями, показывающий как путь через B короче прямого пути Промпт: “educational illustration showing triangle of three cities A, B, C, direct path 100km vs indirect path through B (30+30=60km), road map style, clear distance labels, modern clean design”

Флойд-Уоршелл делает именно это, но систематически: проверяет ВСЕ возможные промежуточные вершины для ВСЕХ пар городов.

Магия в том, что мы рассматриваем промежуточные вершины по порядку: сначала только через вершину 0, потом через 0 и 1, потом через 0, 1 и 2… И так до конца.

📐 Формальное определение

Пусть dist[i][j][k] = кратчайшее расстояние от i до j, используя только вершины {0, 1, …, k} как промежуточные.

Рекуррентная формула:

dist[i][j][k] = min(
    dist[i][j][k-1],           // не используем k
    dist[i][k][k-1] + dist[k][j][k-1]  // идём через k
)

Базовый случай: dist[i][j][-1] = вес ребра (i,j) если оно есть, иначе ∞

Оптимизация пространства: можем использовать только dist[i][j], обновляя “на месте”:

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Временная сложность: O(n³)
Пространственная сложность: O(n²)

🔍 Примеры с разбором

Пример 1: Простой граф из 4 вершин

Исходная матрица расстояний:

    0  1  2  3
0 [ 0  5  ∞  10]
1 [ ∞  0  3   ∞]
2 [ ∞  ∞  0   1]
3 [ ∞  ∞  ∞   0]

[МЕДИА: image_02] Описание: Граф из 4 вершин с весами рёбер и пошаговое выполнение алгоритма Промпт: “step-by-step Floyd-Warshall algorithm execution, 4 vertices graph with weighted edges, matrix transformations at each k iteration, educational diagram, clean mathematical style”

Итерация k=0 (через вершину 0):

dist[1][3] = min(∞, dist[1][0] + dist[0][3]) = min(∞, ∞ + 10) = ∞
dist[2][1] = min(∞, dist[2][0] + dist[0][1]) = min(∞, ∞ + 5) = ∞

Ничего не изменилось, так как нет путей К вершине 0.

Итерация k=1 (через вершину 1):

dist[0][2] = min(∞, dist[0][1] + dist[1][2]) = min(∞, 5 + 3) = 8
dist[0][3] = min(10, dist[0][1] + dist[1][3]) = min(10, 5 + ∞) = 10

Итерация k=2 (через вершину 2):

dist[0][3] = min(10, dist[0][2] + dist[2][3]) = min(10, 8 + 1) = 9
dist[1][3] = min(∞, dist[1][2] + dist[2][3]) = min(∞, 3 + 1) = 4

Итерация k=3: ничего не меняется.

Финальная матрица:

    0  1  2  3
0 [ 0  5  8  9]
1 [ ∞  0  3  4]
2 [ ∞  ∞  0  1]
3 [ ∞  ∞  ∞  0]

Пример 2: Обнаружение отрицательных циклов

def floyd_warshall_with_negative_cycles(graph):
    n = len(graph)
    dist = [[float('inf') if i != j else 0 
             for j in range(n)] for i in range(n)]
    
    # Инициализация
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    
    # Основной алгоритм
    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]
    
    # Проверка на отрицательные циклы
    for i in range(n):
        if dist[i][i] < 0:
            return None, "Найден отрицательный цикл!"
    
    return dist, "OK"

🎮 Практика

Базовый уровень 🟢

Задача 1: Дана матрица смежности графа. Найди кратчайшие расстояния между всеми парами вершин:

    A  B  C
A [ 0  2  ∞]
B [ ∞  0  3]  
C [ 1  ∞  0]

Задача 2: В социальной сети 4 человека: Alice, Bob, Carol, Dave. Связи: Alice→Bob (1), Bob→Carol (1), Carol→Dave (1), Dave→Alice (1). Найди минимальное число “рукопожатий” между всеми парами.

Задача 3: Есть 3 валюты: USD, EUR, RUB. Курсы обмена заданы матрицей. Можно ли получить прибыль от арбитража?

Продвинутый уровень 🟡

Задача 4: Реализуй восстановление самого пути (не только расстояния). Используй матрицу предков.

Задача 5: Модифицируй алгоритм для работы с графом, где рёбра имеют не только вес, но и “пропускную способность”. Нужно найти путь с минимальной стоимостью при ограничении на минимальную пропускную способность.

Задача 6: В игре-стратегии юниты могут двигаться по клеткам. Некоторые клетки - болота (стоимость 3), некоторые - дороги (стоимость 1), некоторые - горы (непроходимы). Найди оптимальные маршруты между всеми важными точками на карте 8×8.

Челлендж 🔴

Задача 7: Netflix Problem: У стримингового сервиса есть серверы в разных городах. Пользователь подключается к ближайшему серверу, но иногда выгоднее маршрутизировать трафик через промежуточные серверы. Учитывая задержки между серверами и пропускную способность, найди оптимальную стратегию маршрутизации.

Задача 8: Crypto Arbitrage: На разных биржах криптовалюты торгуются по разным курсам. Есть комиссии за переводы между биржами. Найди максимально прибыльный цикл арбитража (если он существует).

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

❌ Ошибка: Неправильный порядок циклов - внешний цикл не по k

# НЕПРАВИЛЬНО!
for i in range(n):
    for k in range(n):
        for j in range(n):

✅ Правильно: k должно быть внешним циклом - мы рассматриваем промежуточные вершины по очереди 💡 Почему: иначе мы можем использовать вершину k как промежуточную до того, как вычислили оптимальные пути ДО неё

❌ Ошибка: Забыть инициализировать диагональные элементы нулями ✅ Правильно: dist[i][i] = 0 для всех i 💡 Почему: расстояние от вершины до себя всегда 0

❌ Ошибка: Использовать int вместо float(‘inf’) для недостижимых вершин ✅ Правильно: Используй float(‘inf’) или очень большое число 💡 Почему: иначе арифметические операции могут дать неожиданные результаты

❌ Ошибка: Не проверять отрицательные циклы ✅ Правильно: После алгоритма проверь, есть ли dist[i][i] < 0 💡 Почему: отрицательный цикл означает, что можно получить сколь угодно короткий путь

❌ Ошибка: Модифицировать матрицу во время итерации по k-му элементу той же итерации ✅ Правильно: В пределах одной итерации k все обновления независимы 💡 Почему: мы используем значения dist[i][k] и dist[k][j], вычисленные на предыдущих итерациях

🎓 Главное запомнить

✅ Суть: Систематически проверяем все промежуточные вершины для всех пар ✅ Формула: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
✅ Сложность: O(n³) времени, O(n²) памяти ✅ Применение: Когда нужны кратчайшие пути между ВСЕМИ парами вершин

🔗 Связь с другими темами

Флойд-Уоршелл - это пример динамического программирования на графах. Он связан с:

🔄 Алгоритм Дейкстры - для одной вершины, Флойд-Уоршелл - для всех пар 📊 Умножение матриц - есть связь с возведением матрицы смежности в степень
🔍 Транзитивное замыкание - исходная задача Уоршелла 💰 Арбитраж - поиск отрицательных циклов в логарифмическом пространстве курсов валют 🎮 Игровые алгоритмы - предвычисление расстояний для AI