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

В информатике алгоритм Флойда–Уоршелла (также известный как алгоритм Флойда, алгоритм Роя–Уоршелла, алгоритм Роя–Флойда или алгоритм WFI) - это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин. Хотя он не возвращает детали самих путей, можно реконструировать пути с помощью простых модификаций алгоритма. Варианты алгоритма также могут быть использованы для поиска транзитивного замыкания отношения или (в связи с системой голосования Шульце) наиболее широких путей между всеми парами вершин взвешенного графа.