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

Алгоритм Флойда-Воршелла — алгоритм динамічного програмування для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблений в 1962 році Робертом Флойдом і Стівеном Воршеллом.

Алгоритм

Нехай вершини графа $G=(V,\; E),\; |V| = n$ пронумеровані від 1 до $n$ і введено позначення $d_{i j}^{k}$ для довжини найкоротшого шляху від $i$ до $j$, який окрім самих вершин $i,\; j$ проходить тільки через вершини $1 \ldots k$. Очевидно, що $d_{i j}^{0}$ — довжина (вага) ребра $(i,\;j)$, якщо воно існує (в іншому разі його довжина може бути позначена як $\infty$)

Існує два варіанти значення $d_{i j}^{k},\;k \in \mathbb (1,\;\ldots,\;n)$:

1. Найкоротший шлях між $i,\;j$ не проходить через вершину $k$, тоді $d_{i j}^{k}=d_{i j}^{k-1}$

1. Існує більш короткий шлях між $i,\;j$, що проходить через $k$, тоді він спочатку йде від $i$ до $k$, а потім від $k$ до $j$. У цьому випадку, очевидно, $d_{i j}^{k}=d_{i k}^{k-1} + d_{k j}^{k-1}$

Таким чином, для знаходження значення функції досить вибрати мінімум з двох позначених значень.

Тоді рекурентна формула для $d_{i j}^k$ має вигляд:

$d_{i j}^0$ — довжина ребра $(i,\;j)$

$d_{i j}^{k} = \min (d_{i j}^{k-1},\; d_{i k}^{k-1} + d_{k j}^{k-1})$

Алгоритм Флойда-Воршелла послідовно обчислює всі значення $d_{i j}^{k}$, $\forall i,\; j$ для $k$ від 1 до $n$. Отримані значення $d_{i j}^{n}$ є довжинами найкоротших шляхів між вершинами $i,\; j$.

Псевдокод

На кожному кроці алгоритм генерує двовимірну матрицю $W$, $w_{ij}=d_{i j}^n$. Матриця $W$ містить довжини найкоротших шляхів між усіма вершинами графа. Перед роботою алгоритму матриця $W$ заповнюється довжинами ребер графа.

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      W[i][j] = min(W[i][j], W[i][k] + W[k][j])

Складність алгоритму

Три вкладені цикли містять операцію, яка виконується сталий час. $\sum_{n,\;n,\;n}O(1) = O(n^3),$ тобто алгоритм має кубічну складність, при цьому простим розширенням можна отримати також інформацію про найкоротші шляхи — крім відстані між двома вузлами записувати в матрицю ідентифікатор першого вузла в дорозі.

Варіації алгоритму

Побудова матриці досяжності

Алгоритм Флойда-Уоршелла може бути використаний для знаходження замикання відносини $E$ по транзитивності. Для цього в якості W[0] використовується бінарна матриця суміжності графа, $({w^0}_{i j})_{n \times n} = 1 \Leftrightarrow (i,\; j) \in E$; оператор min замінюється диз'юнкцією, додавання замінюється кон'юнкцією:

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      W[i][j] = W[i][j] or (W[i][k] and W[k][j])

Після виконання алгоритму матриця W є матрицею досяжності.

Використання бітових масок при реалізації алгоритму дозволяє істотно прискорити алгоритм. У цьому складність алгоритму знижується до $O(n^3/k)$, де $k$ — довжина бітової маски (у моделі обчислень RAM). На практиці, ще більшого прискорення можна досягти, використовуючи такі спеціалізовані набори мікропроцесорних команд, як SSE.

Див. також

• Алгоритм Дейкстри
• Алгоритм Джонсона
• Алгоритм Данцига
• Алгоритм Уоршелла

Посилання

• Реалізіція алгоритму Флойда на С++
• Реалізація алгоритму Флойда на Delphi
• Візуалізатор

Література

• Ананій В. Левітін Розділ 8. Динамічне програмування: Алгоритм Флойда пошуку найкоротших шляхів між усіма парами вершин
• Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Ривест, Кліффорд Штайн «Алгоритми: побудова й аналіз»