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

Алгоритм Флойда — Воршелла
КласЗадача про найкоротший шлях (для зважених графів)
Структура данихГраф
Найгірша швидкодія
Найкраща швидкодія
Просторова складність у найгіршому випадку

В інформатиці, алгоритм Флойда-Воршелла використовується для розв'язання задачі про найкоротший шлях у зваженому графі з додатними або від'ємними вагами ребер (але без від'ємнозначних циклів).[1][2] При звичайній реалізації алгоритм видасть довжини (сумарні ваги) найкоротших шляхів між всіма парами вершин, хоча він не видасть інформацію про самі шляхи. Різні версії алгоритму також використовуються для знаходження транзитивного замикання в відношенні , або (враховуючи Метод Шульце), для знаходження найбільшого шляху (англ. widest path problem) між всіма парами вершин у зваженому графі.

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

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

Алгоритм також називають Алгоритм Флойда, Алгоритм Роя-Воршелла, Алгоритм Роя-Флойда, або Алгоритм WFI.

інші мови