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