Алгоритм Флойда — Воршелла

Алгоритм Флойда — Воршелла

Клас	Задача про найкоротший шлях (для зважених графів)
Структура даних	Граф
Найгірша швидкодія	$O(|V|^{3})$
Найкраща швидкодія	$\Omega (|V|^{3})$
Просторова складність у найгіршому випадку	$\Theta (|V|^{2})$

В інформатиці алгоритм Флойда — Воршелла служить для розв'язання задачі про найкоротший шлях в орієнтованому зваженому графі з додатними або від'ємними вагами ребер (але без негативних циклів).

При звичайній реалізації алгоритм повертає довжини (сумарні ваги) найкоротших шляхів між усіма парами вершин. Модифікація алгоритму може також повертати інформацію про самі шляхи. Різні версії алгоритму також використовують для знаходження транзитивного замикання у відношенні $R$, або для знаходження найширшого шляху між усіма парами вершин у зваженому графі (наприклад, при використанні методу Шульце).

Історія і назва

Алгоритм було опубліковано в звичній сьогодні формі Робертом Флойдом 1962 року. Проте це практично той самий алгоритм, що був опублікований Бернардом Роєм 1959 року і Стівеном Воршеллом 1962 року для знаходження транзитивного замикання в графі, і є досить тісно пов'язаним з алгоритмом Кліні (опублікованим 1956 року) для перетворення детермінованих скінченних автоматів у регулярні вирази. Сучасне формулювання алгоритму як трьох вкладених циклів було вперше подано Пітером Інгерманом 1962 року.

Алгоритм Флойда — Воршелла також відомий як Алгоритм Флойда, Алгоритм Роя — Воршелла, Алгоритм Роя — Флойда, або Алгоритм WFI.

Алгоритм

Алгоритм Воршелла порівнює всі можливі шляхи в графі між кожною парою вершин. Він виконується за $\Theta (|V|^{3})$ порівнянь. Це доволі швидко, враховуючи, що в графі може бути до $\Omega (|V|^{2})$ ребер, і кожну комбінацію буде перевірено. Він виконує це шляхом поступового поліпшення оцінки найкоротшого шляху між двома вершинами, поки оцінка не стає оптимальною.

Нехай є граф $G$ з вершинами $V$, пронумерованими від $1$ до $N$. Крім того, нехай є функція ${\textstyle \mathrm {shortestPath} (i,j,k)}$, яка повертає найкоротший шлях від $i$ до $j$, використовуючи вершини з множини $\{1,2,\ldots ,k\}$ як проміжні у шляху. Маючи таку функцію, нам потрібно знайти найкоротший шлях від кожного $i$ до кожного $j$, використовуючи лише вершини з множини $\{1,2,\ldots ,k+1\}$.

Для кожної з цих пар вершин, найкоротшим шляхом може бути або

1) шлях, у якому є тільки вершини з множини $\{1,2,\ldots ,k\}$,

або

2) шлях, який крізь вершини з множини $\{1,2,\ldots ,k\}$ проходить спочатку від $i$ до $k+1$, а потім від $k+1$ до $j$.

Найкоротший шлях від $i$ до $j$, у якому є тільки вершини від $1$ до $k$, визначається функцією ${\textstyle \mathrm {shortestPath} (i,j,k)}$. Якщо є коротший шлях від $i$ крізь $k+1$ до $j$, то довжина цього шляху буде сумою (конкатенацією) найкоротшого шляху від $i$ до $k+1$ (крізь вершини з $\{1,2,\ldots ,k\}$) та найкоротшого шляху від $k+1$ до $j$ (також крізь вершини з $\{1,2,\ldots ,k\}$).

Якщо позначити вагу ребра від $i$ до $j$ через $w(i,j)$, можна визначити ${\textstyle \mathrm {shortestPath} (i,j,k+1)}$ наступною рекурентною формулою:

База:

${\textrm {shortestPath}}(i,j,0)=w(i,j)$,

рекурентна частина:

${\textrm {shortestPath}}(i,j,k+1)=\min({\textrm {shortestPath}}(i,j,k),\,{\textrm {shortestPath}}(i,k+1,k)+{\textrm {shortestPath}}(k+1,j,k))$

Ця формула є основною частиною алгоритму Флойда — Воршелла. Алгоритм спочатку обчислює ${\textstyle \mathrm {shortestPath} (i,j,k)}$ для всіх пар $(i,j)$ при $k=1$, потім при $k=2$, і т. д. Цей процес продовжується до виконання умови $k=N$ (включно), в результаті чого буде знайдено всі найкоротші шляхи для пар $(i,j)$ крізь будь-які проміжні вершини. Псевдокод для цієї версії алгоритму:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u, v)
5    dist[u][v] ← w(u, v)  // the weight of the edge (u, v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

Приклад

Наведений вище алгоритм виконується на графі, розташованому ліворуч на малюнку нижче:

Перед першою ітерацією циклу, тобто при $k=0$, усі відомі шляхи відповідають одиничним ребрам у графі. Після кроку $k=1$ алгоритм знаходить шляхи, які проходять через вершину $1$. Зокрема, шлях $2\rightarrow 1\rightarrow 3$ замінить шлях $2\rightarrow 3$, що проходить через меншу кількість ребер, але є довшим (у сенсі ваги). Після $k=2$ знайдено шляхи, що проходять через вершини $\{1,2\}$. Червоні та блакитні обведення показують, як шлях $4\rightarrow 2\rightarrow 1\rightarrow 3$ складається зі шляхів $4\rightarrow 2$ та $2\rightarrow 1\rightarrow 3$, визначених на попередніх ітераціях. Шлях $4\rightarrow 2\rightarrow 3$ не розглядається, тому що найкоротшим шляхом від $2$ до $3$ на даному етапі є $2\rightarrow 1\rightarrow 3$. Після $k=3$ знайдено шляхи, що проходять через $\{1,2,3\}$. Нарешті, після $k=4$, знайдено всі найкоротші шляхи.

При негативних циклах

Негативний цикл — це цикл, в якому сума всіх ребер є меншою за нуль. Між будь-якою парою вершин $(i,j)$, що входять до негативного циклу, не існує найкоротшого шляху, оскільки довжина шляху між ними може бути наскільки завгодно малою (від'ємною). Для отримання осмисленого результату, алгоритм Флойда — Воршелла передбачає відсутність у графі негативних циклів. Тим не менш, якщо негативні цикли існують, алгоритм Флойда — Воршелла можна використати, щоб виявити їх. Інтуїтивно можна навести наступні міркування:

• Алгоритм Флойда — Воршелла багаторазово змінює довжини шляху між усіма парами вершин $(i,j)$, включаючи ті, де $i=j$;
• Початкова довжина шляху $(i,i)$ рівна 0;
• Шлях $i\rightarrow j\rightarrow \ldots \rightarrow i$ може покращити початкову довжину, якщо він має довжину меншу за нуль, тобто позначає негативний цикл;
• Таким чином, після виконання алгоритму, найкоротший шлях $(i,i)$ буде від'ємним, якщо існує негативний цикл — шлях від'ємної довжини від $i$ назад до $i$.

Отже, для виявлення негативних циклів з використанням алгоритму Флойда — Воршелла можна перевірити діагональ матриці шляхів. Присутність від'ємного числа означатиме, що графік містить щонайменше один негативний цикл. Під час виконання алгоритму присутність негативного циклу може викликати появу чисел, які на порядки перевищують модуль найменшої від'ємної ваги ребра. Щоб уникнути проблем переповнення або зникнення порядку, потрібно перевіряти діагональ матриці шляхів у внутрішньому циклі алгоритму. Очевидно, що в неорієнтованому графі негативне ребро створює негативний цикл за участі прилеглих до ребра вершин. Якщо розглядати граф з попереднього прикладу як неорієнтований, то послідовність ребер $4\rightarrow 2\rightarrow 4$ утворюють цикл довжини $-2$.

Знаходження шляху

Алгоритм Флойда — Воршелла зазвичай знаходить тільки довжини шляхів між усіма парами вершин. За допомогою простих змін можна створити функцію для відновлення фактичного шляху між будь-якими двома кінцевими точками вершин. У наївному підході можна зберігати шлях від кожної вершини до кожної вершини, але це не обов'язково, і насправді дуже витратно щодо пам'яті. Натомість, дерево найкоротших шляхів може бути обчисленим для кожної вершини за час $\Theta (|E|)$, використовуючи $\Theta (|V|)$ пам'яті для збереження кожного дерева, що дозволить ефективно відтворити шлях між будь-якими двома з'єднаними вершинами.

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction()
   for each edge (u, v)
      dist[u][v] ← w(u, v)  // the weight of the edge (u,v)
      next[u][v] ← v
   for k from 1 to |V| // standard Floyd-Warshall implementation
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]
               next[i][j] ← next[i][k]

procedure Path(u, v)
   if next[u][v] = null then
       return []
   path ← [u]
   while u ≠ v
       u ← next[u][v]
       path.append(u)
   return path

Аналіз

Нехай $n$ дорівнює кількості вершин $|V|$. Щоб знайти усі $n^{2}$ значень ${\textstyle \mathrm {shortestPath} (i,j,k)}$ (для всіх пар $(i,j)$), виходячи з відомих ${\textstyle \mathrm {shortestPath} (i,j,k-1)}$, потрібно $2n^{2}$ операцій. Оскільки ми починаємо з ${\textrm {shortestPath}}(i,j,0)=w(i,j)$ та рахуємо послідовність $n$ матриць ${\textstyle \mathrm {shortestPath} (i,j,1),\ \mathrm {shortestPath} (i,j,2),\ \ldots \ ,\mathrm {shortestPath} (i,j,n)}$, кількість операцій становить $n\cdot 2n^{2}=2n^{3}$, і складність алгоритму становить $\Theta (n^{3})$.

Застосування

Алгоритм Флойда — Воршелла можна використовувати для вирішення таких задач:

• Знаходження найкоротших шляхів у напрямленому графі.
• Знаходження транзитивних замикань у напрямленому графі. В оригінальному формулюванні (Воршелла), граф є незважений і представлений булевою матрицею. Операції додавання і мінімуму замінені на логічні AND i OR.
• Знаходження регулярних виразів, що позначають регулярні граматики, які приймаються скінченним автоматом (Алгоритм Кліні, який є узагальненням алгоритму Флойда — Воршелла).
• Невиродженість матриці в методі Гауса
• Оптимальна маршрутизація. У такій постановці задача полягає у знаходженні шляху з максимальним потоком між двома вершинами. Це означає, що замість мінімумів, як у псевдокоді вище, шляхи оптимізуються по максимумах. Вагами ребер задаються фіксовані обмеження на величину потоку. Загальний потік вздовж шляху характеризується ребром з найменшим пропусканням, тому операція додавання замінюється на взяття мінімуму.
• Знаходження найдовшого шляху.
• Швидкі обрахунки у Pathfinder network.
• Розрахунок канонічних форм матриць меж різності (DBM).

Реалізація

Реалізація алгоритму доступна багатьма мовами:

• C++, в бібліотеці boost::graph [Архівовано 13 січня 2008 у Wayback Machine.]
• C#, в QuickGraph [Архівовано 17 березня 2010 у Wayback Machine.] та QuickGraphPCL [Архівовано 11 червня 2020 у Wayback Machine.]
• Java, у бібліотеці Apache Commons Graph [Архівовано 12 травня 2013 у Wayback Machine.]
• JavaScript, у бібліотеці Cytoscape
• MATLAB, у пакеті Matlab_bgl [Архівовано 17 серпня 2013 у Wayback Machine.]
• Perl, в модулі Graph [Архівовано 8 жовтня 2013 у Wayback Machine.]
• Python, в бібліотеці NetworkX та модулі scipy.sparse.csgraph [Архівовано 11 червня 2020 у Wayback Machine.] бібліотеки SciPy
• R, в пакетах e1071 [Архівовано 27 червня 2015 у Wayback Machine.] та Rfast [Архівовано 18 липня 2020 у Wayback Machine.]

Порівняння з іншими алгоритмами

Алгоритм Флойда — Воршелла добре підходить для обчислення шляху між усіма парами вершин у щільних графах, в яких більшість або всі пари вершин з'єднані ребрами. Для розріджених графів з невід'ємними вагами ребер краще використовувати алгоритм Дейкстри для кожної можливої вихідної вершини, оскільки складність алгоритму Дейкстри ($O(|E||V|+|V|^{2}\log |V|)$ з використанням купи Фібоначчі) є кращою, ніж $O(|V|^{3})$ — складність алгоритму Флойда — Воршелла, коли $|E|$ набагато менше від $|V|^{2}$. Для розріджених графів з негативними ребрами, але без негативних циклів, може бути використаний алгоритм Джонсона з тим самим асимптотичним часом роботи, що й повторюваний алгоритм Дейкстри.

Є також відомі алгоритми, що використовують швидке множення матриць для пришвидшення процесу пошуку найкоротшого шляху між усіма парами вершин у щільних графах. Проте у них робиться додаткове обмеження на ваги ребер (вони повинні бути малими цілими). Крім того, через високі сталі коефіцієнти у виразі складності, вони можуть забезпечити пришвидшення відносно алгоритму Флойда — Воршелла лише для дуже великих графів.

Додатково

• Interactive animation of the Floyd–Warshall algorithm [Архівовано 25 серпня 2002 у Wayback Machine.]
• The Floyd–Warshall algorithm in C#, as part of QuickGraph [Архівовано 21 січня 2018 у Wayback Machine.]
• Visualization of Floyd's algorithm [Архівовано 30 травня 2015 у Wayback Machine.]