Алгоритм Флойда — Уоршелла — это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом рёбер (но без отрицательных циклов). 4

За одно выполнение алгоритма находятся длины (суммарные веса) кратчайших путей между всеми парами вершин. 24 Хотя он не возвращает детали самих путей, можно реконструировать их с помощью простых модификаций алгоритма. 2

Принцип работы заключается в сравнении всех возможных путей через граф между каждой парой вершин. 2 Это достигается путём постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной. 2

Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. 4