Алгоритм Флойда-Уоршелла: найкоротші шляхи між усіма парами за O(n³)

1. Задача про найкоротші шляхи між усіма парами

Маємо зважений орієнтований граф G = (V, E) з n = |V| вершинами та функцією ваги ребер w(u, v) (ваги можуть бути від'ємними, доки не існує циклу з від'ємною сумарною вагою). Задача найкоротших шляхів між усіма парами (APSP) вимагає знайти відстань найкоротшого шляху d(i, j) для кожної впорядкованої пари вершин (i, j).

Наївний підхід — запустити алгоритм з однією джерельною вершиною, як-от Беллмана-Форда, з кожної вершини — коштує O(V² · E) з Беллманом-Фордом, оскільки має толерувати від'ємні ваги. Флойд-Уоршелл розв'язує ту саму задачу, включно з від'ємними вагами, за плоску O(V³) незалежно від кількості ребер графа, що робить його найпростішим коректним вибором для щільних графів.

2. Формулювання через динамічне програмування

Трюк, відкритий незалежно Робертом Флойдом і Стівеном Уоршеллом у 1962 році (спираючись на споріднену ідею Бернара Руа 1959 року), полягає в тому, щоб думати про шляхи не за їх довжиною, а за тим, які проміжні вершини їм дозволено відвідувати.

Визначимо dist[k][i][j] як довжину найкоротшого шляху від i до j, що використовує як проміжні зупинки лише вершини з множини {1, 2, …, k} (самі i та j завжди дозволені як кінцеві точки, незалежно від k).

Оскільки dist[k][·][·] залежить лише від dist[k-1][·][·], всю тривимірну таблицю можна згорнути в одну матрицю n×n, що оновлюється на місці — саме ця "матриця" і стоїть за компактною реалізацією алгоритму.

3. Алгоритм і псевдокод

FLOYD-WARSHALL(W):  // W = матриця ваг n×n, W[i][i] = 0, W[i][j] = ∞ якщо ребра немає
  dist = copy(W)
  next = матриця n×n, next[i][j] = j якщо ребро (i,j) існує інакше null   // для відновлення шляху

  для k = 1 до n:            // дозволена проміжна вершина
    для i = 1 до n:
      для j = 1 до n:
        якщо dist[i][k] + dist[k][j] < dist[i][j]:
          dist[i][j] = dist[i][k] + dist[k][j]
          next[i][j] = next[i][k]     // маршрут через k

  повернути dist, next

Весь алгоритм — це рівно три вкладені цикли з одним порівнянням і оновленням усередині — без черги з пріоритетом, без рекурсії, без допоміжних структур даних. Ця простота значною мірою пояснює, чому він залишається стандартним прикладом у підручниках для навчання динамічного програмування на графах.

4. Коректність: індукція за проміжними вершинами

Доведення — це чітка індукція за k, розміром множини дозволених проміжних вершин:

• Базовий випадок (k = 0): без дозволених проміжних вершин єдині допустимі "шляхи" — прямі ребра або залишання на місці, що є саме початковою матрицею ваг W.
• Індуктивний крок: припустимо, dist[k-1][i][j] коректно є найкоротшим {1..k-1}-обмеженим шляхом для всіх i, j. Будь-який найкоротший {1..k}-обмежений i-j шлях або зовсім уникає k (вартість = dist[k-1][i][j]), або відвідує k. Якщо він відвідує k, оскільки найкоротший шлях ніколи не відвідує одну й ту саму вершину двічі, він відвідує k рівно один раз, розбиваючись на сегмент i→k і сегмент k→j, кожен з яких сам є найкоротшим {1..k-1}-обмеженим шляхом (інакше можна було б замінити коротшим підшляхом і покращити весь шлях — стандартний аргумент "оптимальної підструктури"). Тому його вартість дорівнює саме dist[k-1][i][k] + dist[k-1][k][j].
• Взяття мінімуму цих двох випадків дає саме те рекурентне співвідношення, що використовується в алгоритмі — отже, dist[k][i][j] коректно підтримується на кожному кроці, і dist[n][i][j] є справжньою необмеженою відстанню найкоротшого шляху.

5. Складність

Оскільки час виконання не залежить від кількості ребер, Флойд-Уоршелл найкраще підходить для щільних графів (E близько до V²), де він відповідає або переважає запуск Дейкстри V разів. На розріджених графах запуск Дейкстри на основі купи з кожної вершини або спеціалізований алгоритм Джонсона асимптотично швидший — див. порівняльну таблицю в кінці.

6. Виявлення від'ємних циклів

На відміну від Дейкстри, Флойд-Уоршелл коректно обробляє від'ємні ваги ребер — доки в графі немає циклу з від'ємною вагою (циклу, чия сумарна вага менша за нуль, що зробило б "найкоротший шлях" невизначеним, оскільки можна нескінченно кружляти навколо нього, щоб необмежено зменшувати загальну вартість).

Ця вбудована діагностика — одна з причин, чому Флойд-Уоршелл залишається популярним, навіть коли граф достатньо розріджений, щоб алгоритм Джонсона був швидшим: перевірка від'ємного циклу приходить практично безкоштовно, тоді як підходи на основі Беллмана-Форда потребують явного додаткового проходу релаксації.

7. Відновлення шляху

Сама лише матриця відстаней не каже, які вершини відвідує найкоротший шлях. Стандартне рішення — підтримувати паралельну матрицю next[i][j] (як показано в псевдокоді вище), що записує "наступну вершину, до якої йти на найкоротшому шляху від i до j":

RECONSTRUCT-PATH(next, i, j):
  якщо next[i][j] == null: повернути []       // шляху не існує
  path = [i]
  поки i != j:
    i = next[i][j]
    path.push(i)
  повернути path

Кожне оновлення next[i][j] = next[i][k] в основному циклі просто каже: "якщо тепер швидше маршрутизувати i→j через k, то перший крок з i має бути тим самим, яким уже був перший крок з i до k" — невелика, але суттєва деталь, яку багато наївних реалізацій забувають.

8. Флойд-Уоршелл проти повторної Дейкстри та алгоритму Джонсона

Алгоритм Джонсона поєднує переваги обох підходів на розріджених графах: він запускає один прохід Беллмана-Форда, щоб обчислити потенціали вершин, які перезважують кожне ребро до невід'ємного значення, не змінюючи, які шляхи найкоротші, а потім запускає Дейкстру з кожної вершини на перезваженому графі. Для щільних графів (E ≈ V²) член V·E log V алгоритму Джонсона все одно наближається до V³ log V, тому звичайний Флойд-Уоршелл з O(V³) — без накладних витрат на перезважування та з набагато простішим кодом — зазвичай перемагає на практиці до кількох сотень вершин, що й пояснює, чому він залишається стандартним вибором, який викладають першим і використовують найчастіше для графів помірного розміру, як-от дорожні мережі, ігрові карти та невеликі й середні інфраструктурні топології.