Пошук найкоротшого шляху
23

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

 

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