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

Шляхи як множини дозволених проміжних вершин

В задачі пошуку найкоротших шляхів між усіма парами вершин у зваженому спрямованому графі з n = |V| вершинами, задача полягає в тому, щоб знайти відстань d(i, j) між кожною парою вершин. Роберт Флойд та Стівен Варшаль у 1962 році знайшли хитромудрий спосіб: замість того, щоб думати про шляхи за довжиною, потрібно розглядати їх через призму дозволених проміжних вершин. Визначимо dist[k][i][j] як найкоротший шлях з i до j, використовуючи лише вершини {1, …, k} як проміжні зупинки.

dist[0][i][j] = w(i,j) якщо існує ребро, 0 якщо i=j, інакше ∞ dist[k][i][j] = min( dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j] ) Відповідь: dist[n][i][j] для кожної пари Шлях, що використовує {1..k}, або ніколи не торкається вершини k (з тією ж вартістю, як і раніше), або проходить через неї рівно один раз, розділяючи його на сегменти i→k та k→j. Оскільки dist[k] залежить лише від dist[k−1], весь 3D-масив стискається до однієї n×n матриці, яка оновлюється на місці — три вкладені цикли, без використання черги пріоритетів та рекурсії.

dist[0][i][j] = w(i,j) if edge exists, 0 if i=j, else ∞

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

Answer: dist[n][i][j] for every pair

Правильність, складність та пастка з порядком циклу

Доведення є чистим індукційним доказом по k: припускаючи, що dist[k−1] правильно для всіх i, j, будь-який найкоротший шлях {1..k}-обмежений або уникає k (однакова вартість) або відвідує його точно один раз — аргумент оптимальної підструктури, який робить рекурентне співвідношення точним. Алгоритм працює за часом O(V³) та за простором O(V²) незалежно від кількості ребер, що робить його найкращим вибором на щільних графах, де він відповідає або перевершує Dijkstra V разів. Цикл k повинен бути найзовнішнім — рекурентне співвідношення потребує повного завершення dist[k−1] перед використанням k як нової проміжної зупинки, і зміна порядку циклів безсвірно руйнує правильність.

Негативні цикли майже безкоштовно

На відміну від алгоритму Дейкстри, Floyd-Warshall обережно поводиться з від'ємними вагами ребер, за умови, що сума ваг циклу не є меншою за нуль. Після виконання алгоритму перевірте діагональ: dist[i][i] починається з 0 і може стати негативним лише якщо певний цикл через i має загальну від'ємну вагу — це саме визначення негативного циклу. Ця діагностика є однією з причин, чому Floyd-Warshall залишається популярним навіть на графах, де існує швидший метод: алгоритм Джонсона (Bellman-Ford для перенесення ребер у невід'ємний формат, потім Дейкстра з кожного вершини) перевершує Floyd-Warshall за O(V³) на розріджених графах із від'ємними вагами, а саме O(V²log V + VE), але потребує додаткового явного проходу для такої самої перевірки.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.