Алгоритмы

Floyd-Warshall: Все пары кратчайших путей

Цели урока

  • Понять идею промежуточных вершин
  • Реализовать Floyd-Warshall
  • Восстанавливать пути
  • Знать применения: транзитивное замыкание, диаметр

Предварительные знания

  • Dijkstra
  • Динамическое программирование
  • Dijkstra: кратчайший путь

Представьте навигатор, который должен знать расстояние между ЛЮБЫМИ двумя городами. Предвычислить все заранее - и ответ за O(1)! Floyd-Warshall делает это за O(V³).

  • Предвычисленные таблицы маршрутизации
  • Анализ социальных сетей
  • Оптимизация транспортных сетей
  • Вычисление транзитивного замыкания в БД

Руа, Уоршелл и Флойд в 1962 году

Это один из тех алгоритмов, которые несколько человек нашли почти одновременно. Французский математик Бернар Руа опубликовал основную идею в 1959 году. Стивен Уоршелл, работавший в оборонной компании, опубликовал в 1962 году вариант для транзитивного замыкания, рассуждая о достижимости через промежуточные вершины. В том же году Роберт Флойд опубликовал форму для кратчайших путей в Communications of the ACM, крошечную заметку, едва длиннее самого алгоритма, и прямо связал её с работой Уоршелла. Тройной вложенный цикл с k снаружи, dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]), одинаков в обоих случаях: Уоршелл использовал булевы OR и AND, Флойд использовал min и плюс. Наблюдение, что оба живут на одном шаблоне над разными полукольцами, стало повторяющейся темой в дизайне алгоритмов. Название Floyd-Warshall закрепилось, хотя исторически честнее было бы Roy-Floyd-Warshall.

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

**Задача:** найти кратчайшие пути между ВСЕМИ парами вершин. Запускать Dijkstra V раз? Можно, но есть элегантнее.

**Идея Floyd-Warshall:** постепенно разрешаем использовать больше промежуточных вершин.

**Почему работает:** на шаге k мы проверяем, улучшит ли путь через k-ю вершину. Если да - обновляем.

На шаге k=5 алгоритм проверяет пути:

Реализация

**Оптимизация памяти:** не нужен массив [k], можно обновлять на месте!

СравнениеFloyd-WarshallV × Dijkstra
ВремяO(V³)O(V × (V+E) log V)
Плотный граф (E≈V²)O(V³)O(V³ log V)
Разреженный графO(V³)O(V² log V)
Отрицательные весаДАНЕТ

**Floyd-Warshall лучше** для плотных графов и при отрицательных весах (без циклов). Для разреженных - V раз Dijkstra.

Почему порядок циклов именно k, i, j (а не i, j, k)?

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

**Чтобы восстановить путь**, храним `next[i][j]` - следующую вершину на пути от i к j.

**Обнаружение отрицательного цикла:**

Как Floyd-Warshall обнаруживает отрицательный цикл?

Применения

**1. Транзитивное замыкание графа:**

**2. Минимаксные / максиминные пути:**

**3. Диаметр графа:**

  • **Маршрутизация:** предвычисленные таблицы
  • **Социальные сети:** степени разделения для всех пар
  • **Анализ графов:** центральность, эксцентриситет

Порядок вложенных циклов в Floyd-Warshall не важен - три цикла по N всё равно дают O(V^3) операций, главное проверить все тройки (i, j, k).

Только k во внешнем цикле даёт корректный ответ. Порядок i, j, k или j, k, i даёт неверные dist[i][j], потому что DP-таблица обновляется на месте и порядок определяет, какие подзадачи готовы.

В голове 'три цикла' выглядят симметрично, особенно если уже привыкли к матричному умножению, где порядок не критичен для результата. Но здесь dist[i][k] и dist[k][j] должны соответствовать уровню k-1 на момент обновления - это держится только при k снаружи.

Для сети с 1000 узлами и 500000 рёбрами, что быстрее?

Floyd-Warshall

  • Находит кратчайшие пути между ВСЕМИ парами
  • O(V³) время, O(V²) память
  • Работает с отрицательными весами (без циклов)
  • Порядок циклов: k, i, j - критичен!
  • Лучше для плотных графов

Вопросы для размышления

  • Тот же шаблон 'k снаружи, i и j внутри' встречается в matrix chain multiplication и transitive closure - какая глубинная идея DP объединяет эти задачи?
  • Для разреженного графа с 10000 вершин Floyd-Warshall за O(V^3) = 10^12 операций нереалистичен. Какие сигналы в задаче подсказывают перейти к Johnson's algorithm вместо честного Floyd-Warshall?
  • Транзитивное замыкание получается из Floyd-Warshall заменой min на OR. Какие ещё задачи 'все пары' решаются заменой полукольца (min/+) на другое - и где здесь связь с алгеброй матриц?

Связанные темы

Floyd-Warshall - классика динамического программирования на графах.

  • Dijkstra — Одна вершина → все
  • Bellman-Ford — Одна вершина, отрицательные веса
  • Johnson's Algorithm — Перевзвешивание + Dijkstra

Связанные уроки

  • alg-15-bellman-ford — Bellman-Ford - single-source предшественник
  • alg-14-dijkstra — Dijkstra эффективнее для sparse графов
  • alg-21-dp — Floyd-Warshall - классический DP на 3D таблице
  • alg-17-mst — Transitive closure строится аналогичным DP
  • calc-20-extrema-multi — Многомерная оптимизация - та же идея
  • dist-03-fallacies
Floyd-Warshall: Все пары кратчайших путей

0

1

Войти