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

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

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

інші мови