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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм Флойда-Воршелла — алгоритм динамічного програмування для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблений в 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.

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Література[ред.ред. код]

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