2.4 Алгоритм Флойда-Воршелла
Алгоритм Флойда-Воршелла — алгоритм динамічного програмування для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблений в 1962 році Робертом Флойдом і Стівеном Воршеллом.
Алгоритм
Нехай вершини графа пронумеровані від 1 до і введено позначення для довжини найкоротшого шляху від до , який окрім самих вершин проходить тільки через вершини . Очевидно, що — довжина (вага) ребра , якщо воно існує (в іншому разі його довжина може бути позначена як )
Існує два варіанти значення :
- Найкоротший шлях між не проходить через вершину , тоді
- Існує більш короткий шлях між , що проходить через , тоді він спочатку йде від до , а потім від до . У цьому випадку, очевидно,
Таким чином, для знаходження значення функції досить вибрати мінімум з двох позначених значень.
Тоді рекурентна формула для має вигляд:
— довжина ребра
Алгоритм Флойда-Воршелла послідовно обчислює всі значення , для від 1 до . Отримані значення є довжинами найкоротших шляхів між вершинами .